Libdynamic

[fredrikwidlund]

Libdynamic update

[amadvance]

Hi Fredrik,

It's now a lot better! You can see new graphs at:

http://tommyds.sourceforge.net/beta/libdynamic_update/

It seems also that you can get even better performance in insert, grouping the buckets taking into account the typical cache block size. I did some experiments using a preexisting open addressing implementation for TommyDS. You can see it in the refill_extrusive branch. Graphs at:

http://tommyds.sourceforge.net/beta/refill_extrusive/

Note that it's a bit slower in remove because the table is shrinked while removing objects to reduce the heap allocation.

Ciao, Andrea

[fredrikwidlund]

Hi,

Yes, using cache aligned memory allocations does improve performance a bit. This is done in the pull request I sent by using aligned_alloc() (C11), though the cache line size is hardcoded for now so it needs further refactoring.

Regards, Fredrik

[fredrikwidlund]

But yes, in general, using a "refill" algorithm to remove deleted slots, like you do now as well in your open addressing version, does seem like an improvement.

Regards, Fredrik