I'm making hash table for game with sdl2. Is my hash table has speed problem? Did I go wrong?

Game Development
1

100000 data for each and doing tasks to all data

1062ms add
1477ms search
9ms add no rehash
9ms search no rehash
2430ms delete <-idk why this takes so long time

2

is this a spatial hash table for objects placed in 2D?
or is it just a hash table implementing an ordinary dictionary/set/map data structure?

did you write it yourself, or are you using some existing library? which is it?

I have hypothesis, but not useful to guess yet without more information

did you try to profile your code? do you know how? which platform are you using?

3

I donā€™t know why your deletes are slow without seeing source code, but hereā€™s what SDL3ā€™s hashtable looks like:

A discussion on how it works is here:

4

both,
as a expansion of C structure for objects ex: equipments,HP etc. original structure only have common value like position, size.
and dictionary for callbacks,events also, callback arguments use it.

yes, I wrote it by myself except wyhash.

I guess only 1 loop cause this issue but idk why it is actually cause
just deleting

platform is windows11 64bit

5

I just realized I couldnā€™t benchmark no rehash adding properly.
actually adding no rehash takes 350ms.

generaly hash table takes so long time like this?

6

I watched it, that code is very beautiful and simple.

I think Iā€™m making simple thing to more complicated.
I write my hash table with chaining but not linked list instead, uint8_t *array and uint8_t num
and I stored all data key, value, value_datasize

7

in 10k data
time add 24
time search 1
time delete 30
time add no rehash 5
time search no rehash 1

I understand each add/delete needs O(1) * n
but idk why its like O(n) * n
cash locality problem? ummā€¦

8

Just use profiler, instead of wondering what is going on. :wink:

9

ok buddy but what is your algorithm exactly? or code.

on Windows, you can profile your code on Visual Studio on a line-by-line basis

10

or try stb_ds.h

typesafe dynamic array and hash tables for C, will compile in C++

from

1 Like
11

Recently, Iā€™ve been busy sry for late.

I did a gprof profiling and I realized my hashtable isnā€™t a problem,
but my allocater is a problem.
my free() takes 80% of time.

my allocater has stack of current using pointer.
and when freeing search stack for specific pointer which takes O(n). alloc takes O(1)

I should change this

12

OK I no longer use stack. just array.
now my freeing only takes O(1).