Delete performance would benefit from improvement

[lkarlslund]

Very nice library for concurrent maps! For scenarios where you need to delete keys one at a time (not batching), the current performance makes it unusable.

I have an analysis application (https://github.com/lkarlslund/adalanche) and I've tried replacing some of the maps with yours (adding unsafe.Pointer in my fork).

With a nasty workaround where I don't delete keys, but set the value to a deleted flag, it works fairly good. But this is not the way.

Also looking at your code, I'm curious how you distinguish from a hash which is ^0 and the "marked" value which is the same?

[alphadose]

@lkarlslund agreed regarding the performance of deletion, I will make deletion lazy in nature (items will be deleted during Set()) and Del() will just add a marked node in front of the node we want deleted. Then during next iteration on that part of the map, all delete marked nodes will be removed with a CAS

Also looking at your code, I'm curious how you distinguish from a hash which is ^0 and the "marked" value which is the same?

Currently they are indistinguishable. One of the things in my TODO list was to reserve the first bit for all keyhashes to mark whether a node is deleted or not. Let me try this out then get back to you.

[lkarlslund]

I haven't looked at the internals, but it looks like you're pushing a deletion node before the node that should be deleted. Why not just mark this node for deletion directly? Or is that what you want to do with using one bit, so you can preserve ordering at the same time?

[alphadose]

@lkarlslund

Or is that what you want to do with using one bit, so you can preserve ordering at the same time?

I will use index masking to use only the last 63 bits for comparison. Here is an example snippet for the same

const mask uintptr = 1 << 63 - 1

// comparison
if a.KeyHash & mask > b.KeyHash & mask { // do something after comparison }

// check for deletion by checking the first bit
if a.KeyHash & (1 << 63) { println("item = deleted") } 

I haven't looked at the internals, but it looks like you're pushing a deletion node before the node that should be deleted. Why not just mark this node for deletion directly?

This is also a great method but I would have to store an extra field isDeleted of 1 byte uint8 in each node thereby increasing the overall size of the map. Thats why I add a marked deleted node in front of a node which I want to delete and then actually remove it lazily during traversal.

In my opinion both methods are good, I will just check the performance of both approaches and then implement one.

[alphadose]

@lkarlslund deletion performance has improved for single elements with https://github.com/alphadose/haxmap/commit/5a395382a92ea3bbfaf5597be71b9e5b94f39763