Skip to content

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

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.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

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