Skip to content

delete() does not decrement used-bucket metadata, causing false load-factor growth and unsafe resize behavior across transferred map instances #57

@BLaurent

Description

@BLaurent

Hi,
After doing a lot of testing, this might be an issue.

Version: shared-memory-datastructures@1.0.0-alpha.9

Details:

ShareableMap.set() increments the "used buckets" counter when inserting into an empty bucket, but delete() never decrements it when a bucket becomes empty.
Because load factor is based on usedBuckets / buckets, this counter drifts upward during insert/delete churn, even when size returns to 0. That triggers unnecessary doubleIndexStorage() calls.
In multi-thread usage with toTransferableState() / fromTransferableState(), resize is unsafe: doubleIndexStorage() swaps this.indexMem on only one instance, so other instances still read/write the old index buffer.

Test 1:

import { ShareableMap } from 'shared-memory-datastructures';
const m = new ShareableMap({ expectedSize: 64, averageBytesPerValue: 16 });
for (let i = 0; i < 200; i++) {
  for (let j = 0; j < 20; j++) m.set(`${i}:${j}`, 'v');
  for (let j = 0; j < 20; j++) m.delete(`${i}:${j}`);
  if (i % 20 === 0) {
    console.log({
      iter: i,
      size: m.size,
      bucketsInUse: m.getBucketsInUse(),
      bucketCount: m.buckets,
    });
  }
}
console.log('final', {
  size: m.size,
  bucketsInUse: m.getBucketsInUse(),
  bucketCount: m.buckets,
});

Output:

{ iter: 0, size: 0, bucketsInUse: 18, bucketCount: 86 }
{ iter: 20, size: 0, bucketsInUse: 230, bucketCount: 329 }
{ iter: 40, size: 0, bucketsInUse: 395, bucketCount: 653 }
{ iter: 60, size: 0, bucketsInUse: 320, bucketCount: 1301 }
{ iter: 80, size: 0, bucketsInUse: 720, bucketCount: 1301 }
{ iter: 100, size: 0, bucketsInUse: 160, bucketCount: 2597 }
{ iter: 120, size: 0, bucketsInUse: 560, bucketCount: 2597 }
{ iter: 140, size: 0, bucketsInUse: 960, bucketCount: 2597 }
{ iter: 160, size: 0, bucketsInUse: 1360, bucketCount: 2597 }
{ iter: 180, size: 0, bucketsInUse: 1755, bucketCount: 2597 }
final { size: 0, bucketsInUse: 200, bucketCount: 5189 }

Observed:

  • size repeatedly returns to 0
  • bucketsInUse keeps growing
  • bucketCount grows (rehashes happen) despite map being effectively empty after each cycle

Test 2:

import { ShareableMap } from 'shared-memory-datastructures';
const a = new ShareableMap({ expectedSize: 8, averageBytesPerValue: 16 });
const b = ShareableMap.fromTransferableState(a.toTransferableState());
a.set('before', 'ok');
console.log('b sees before:', b.get('before')); // "ok"
a.doubleIndexStorage();
console.log('same index buffer after resize?', a.indexMem === b.indexMem); // false
a.set('after', 'new');
console.log('a sees after:', a.get('after')); // "new"
console.log('b sees after:', b.get('after')); // undefined

Output:

b sees before: ok
same index buffer after resize? false
a sees after: new
b sees after: undefined

Expected:

  • delete() keeps used-bucket metadata consistent.
  • Rehash should not be triggered by stale metadata.
  • If instances are intended to share state across workers, resizing should remain coherent across instances.

Actual:

  • Used-bucket metadata drifts upward under churn.
  • False load-factor triggers rehash/resizes.
  • After resize, transferred instances can diverge (one points to a new index buffer, others to the old one), producing missing keys / inconsistent reads.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions