gephi / gephi/graphstore

Adjacency index allocates one int[] per edge; use a primitive long→int map when parallel edges are disabled.

Open
#279 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Java
Stars
93
Forks
34
Avg merge
18h 53m
Merged PRs (30d)
13

Description

## Summary

The primary edge index, `longDictionary`, is typed `Long2ObjectOpenCustomHashMap[]`. Every edge inserts a `new int[]{ storeId }` as the map value, so a non-parallel graph carries one tiny `int[]` object per edge purely as boxing. Measured overhead is ~28 bytes per edge for the array object + reference, versus ~4 bytes for a primitive value — roughly 230 MB of extra heap per 10M edges. The multi-element array is only needed when parallel edges of the same type are enabled, which is **not** the default. For the default configuration, a primitive `Long2IntOpenCustomHashMap` (storeId as value) removes the per-edge allocation entirely.

## Environment

- `org.gephi:graphstore` `0.8.7-SNAPSHOT`, commit `5028d21`
- Build target JDK 17; measured on OpenJDK 21, compressed oops, default object alignment

## Where

Field declaration (`src/main/java/org/gephi/graph/impl/EdgeStore.java:68`):

```java
protected Long2ObjectOpenCustomHashMap[] longDictionary;
```

Allocation per edge in `addToDico` (`EdgeStore.java:720`):

```java
if (dicoValue == null) {
dicoValue = new int[] { edge.storeId }; // one int[] per edge
} else {
dicoValue = Arrays.copyOf(dicoValue, dicoValue.length + 1); // parallel-edge growth
dicoValue[dicoValue.length - 1] = edge.storeId;
}
dico.put(longId, dicoValue);
```

The array carries more than one element only in the parallel-edge path; `removeFromDico` (`EdgeStore.java:685`) confirms the common case is `dicoValue.length == 1`. Roughly twenty read sites (`get(...)`, `isAdjacent`, mutual-edge detection) currently read `index[0]` from these arrays (`EdgeStore.java:538–600`, `:926`, `:1177–1186`).

## Why it matters

This is a pure-overhead allocation on the default path: for every edge in a non-parallel graph, the map stores a one-element array whose only payload is a single `int`.

### Measured memory (10M elements)

| Storage | Heap | Per element |
|---|---|---|
| `Object[]` of `int[1]` (current value shape) | ~267 MB | ~28 bytes |
| `int[]` equivalent | ~38 MB | ~4 bytes |

So the array-boxing of the dictionary values alone is on the order of 230 MB per 10M edges, before counting the map's own bucket overhead (which is the same either way). There is also GC pressure from millions of short-lived-ish small arrays, and a second pointer hop on every lookup. (The parallel-edge `Arrays.copyOf(..., len+1)` growth is O(k²) per pair, but k is typically tiny, so that's secondary.)

Measurement harness

```java
public class Mem {
static final int N = 10_000_000;
static long used(){ Runtime r = Runtime.getRuntime();
for (int i=0;i<4;i++){ System.gc(); try{Thread.sleep(80);}catch(Exception e){} }
return r.totalMemory() - r.freeMemory(); }
public static void main(String[] a){
long base = used();
Object[] arr1 = new Object[N];
for (int i=0;i

## Proposed direction

When `!configuration.isEnableParallelEdgesSameType()` (the default), back `longDictionary` with a primitive `Long2IntOpenCustomHashMap` keyed by `longId` → `storeId`, using `NULL_ID` as the default return value. This drops the per-edge `int[]` entirely. Keep the existing `Long2ObjectOpenCustomHashMap` only when parallel edges are enabled.

The cleanest packaging is probably a small internal abstraction (e.g. an `AdjacencyIndex` with `get(longId)`, `put(longId, storeId)`, `remove(longId, storeId)`) with two implementations selected by configuration, so the ~20 call sites stop touching `int[]` directly and instead get back a single storeId in the common case. That keeps the parallel-edge logic isolated to one implementation.

The value type is read in many places, so this is a moderate refactor rather than a drop-in swap. The payoff is the full ~230 MB/10M-edges saving on the default configuration plus reduced GC churn.

A larger alternative worth the maintainers' consideration: parallel edges between a pair already coexist in the intrusive `headOut`/`headIn` adjacency lists, so in principle parallel-edge resolution could walk those chains and the dictionary could always store a single head storeId. That would unify both configurations on a primitive map but is a deeper change with its own trade-offs.

## Scope / risk

- Confined to `EdgeStore`'s index; no public API change.
- Parallel-edge configuration keeps current behavior via the existing array-backed path.
- Serialization of the index (if persisted) needs a matching read/write path; the wire format can stay unchanged.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.