Handmade Hero»Forums»Code
Sebastian
6 posts
Day 55 hash table bug
Edited by Sebastian on
After switching to signed ints for coordinates, tilechunk.x == 0 is now valid, but hash map uses x==0 as the "flag" for empty slots. Need another flag.

EDIT: oops, someone mentioned it later on.
Kim
Kim Jørgensen
64 posts
Day 55 hash table bug
It would be better to use an array of pointers instead, to avoid the need for checking the X value
Casey Muratori
801 posts / 1 project
Casey Muratori is a programmer at Molly Rocket on the game 1935 and is the host of the educational programming series Handmade Hero.
Day 55 hash table bug
I don't think it would be better, because it means you always have to do two dereferences to get to the first entry, so I'm pretty sure using a pointer table would always be slower. But we'd have to time it.

- Casey
Simon Anciaux
1337 posts
Day 55 hash table bug
I think there still is a problem in the function: when we create a new chunk (the second if) we set the Chunk variable to point to the new chunk, and just before the end of the loop we set again the Chunk using nextInHash which contains 0 and make the loop stops without initializing the new chunk.

Changing this:
1
2
3
4
5
6
if(Arena && (Chunk->TileChunkX != TILE_CHUNK_UNINITIALIZED) && !Chunk->NextInHash))
{
	Chunk->NextInHash = PushStruct(Arena, tile_chunk);
	Chunk = Chunk->NextInHash;
	Chunk->TileChunkX = TILE_CHUNK_UNINITIALIZED;
}

with this:
1
2
3
4
5
if(Arena && (Chunk->TileChunkX != TILE_CHUNK_UNINITIALIZED) && !Chunk->NextInHash))
{
	Chunk->NextInHash = PushStruct(Arena, tile_chunk);
	Chunk->NextInHash->TileChunkX = TILE_CHUNK_UNINITIALIZED;
}

should fix the problem.
Fredrik Forsberg
3 posts
Day 55 hash table bug
Edited by Fredrik Forsberg on Reason: typo
I looked at the loop and I can't see the problem. After creating the new chunk and changing the Chunk pointer to point to the new chunk we would just enter the following if-statement where we initialize the chunk data and break out of the loop.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
do
    {
        if((TileChunkX == Chunk->TileChunkX) &&
           (TileChunkY == Chunk->TileChunkY) &&
           (TileChunkZ == Chunk->TileChunkZ))
        {            
            break;
        }

        if(Arena && (Chunk->TileChunkX != TILE_CHUNK_UNINITIALIZED) && (!Chunk->NextInHash))
        {
            Chunk->NextInHash = PushStruct(Arena, tile_chunk);
            Chunk = Chunk->NextInHash;     //// <-- point to new chunk
            Chunk->TileChunkX = TILE_CHUNK_UNINITIALIZED;    //// <-- flag new chunk as uninitialized
        }
        
        if(Arena && (Chunk->TileChunkX == TILE_CHUNK_UNINITIALIZED))    //// <-- this is now true
        {
            uint32 TileCount = TileMap->ChunkDim*TileMap->ChunkDim;

            Chunk->TileChunkX = TileChunkX;
            Chunk->TileChunkY = TileChunkY;
            Chunk->TileChunkZ = TileChunkZ;
            
            Chunk->Tiles = PushArray(Arena, TileCount, uint32);
            // TODO(casey): Do we want to always initialize?
            for(uint32 TileIndex = 0;
                TileIndex < TileCount;
                ++TileIndex)
            {
                Chunk->Tiles[TileIndex] = 1;
            }

            Chunk->NextInHash = 0;

            break;                  //// <-- break here
        }

        Chunk = Chunk->NextInHash;
    } while(Chunk);


Your suggested fix would cause us an extra run through the loop since the chunk pointer won't be changed to point to the newly created chunk until the very last line. Other than that I can't see any difference (please tell me if I'm wrong, it is 1.20 AM here and I should probably sleep instead of posting things on the internet :P).
Simon Anciaux
1337 posts
Day 55 hash table bug
You're right !
I should have step through the code to check what I was thinking. I'll do that next time. Thanks
Kim
Kim Jørgensen
64 posts
Day 55 hash table bug
Okay Casey.
I meant better, because I think that it would simplify the logic for adding chunks. The impact on performance was not something that I was aware of.

/Kim
Kim
Kim Jørgensen
64 posts
Day 55 hash table bug
However, I am not sure what is meant with “you always have to do two dereferences to get to the first entry” if a pointer table is used. Is it the extra check to see if the value is null, or is TileChunkHash[HashSlot] slower than TileChunkHash + HashSlot?

Here is how I would have done it with a pointer table:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
tile_chunk *Chunk = TileMap->TileChunkHash[HashSlot];
while(Chunk)
{
    if((TileChunkX == Chunk->TileChunkX) &&
       (TileChunkY == Chunk->TileChunkY) &&
       (TileChunkZ == Chunk->TileChunkZ))
    {
        return(Chunk);
    }
    Chunk = Chunk->NextInHash;
}

if(Arena)
{
    Chunk = PushStruct(Arena, tile_chunk);

    uint32 TileCount = TileMap->ChunkDim*TileMap->ChunkDim;

    Chunk->TileChunkX = TileChunkX;
    Chunk->TileChunkY = TileChunkY;
    Chunk->TileChunkZ = TileChunkZ;

    Chunk->Tiles = PushArray(Arena, TileCount, uint32);
    // TODO(casey): Do we want to always initialize?
    for(uint32 TileIndex = 0;
        TileIndex < TileCount;
        ++TileIndex)
    {
        Chunk->Tiles[TileIndex] = 1;
    }

    Chunk->NextInHash = TileMap->TileChunkHash[HashSlot];
    TileMap->TileChunkHash[HashSlot] = Chunk;
}

return(Chunk);


/Kim
Johannes Algelind
3 posts
Day 55 hash table bug
Edited by Johannes Algelind on Reason: I can't read.
First the TileChunkHash will need to be read into the cache in order to get the pointer to the TileChunk, and then the memory where TileChunk is stored will need to be read into the cache.

In the existing code, everything needed is stored in a contiguous block of memory. So once the TileChunk pulled into the cache, all member values are immediately accessible.

[strike]The next TileChunk is also immediately available, since it's stored right next to the current one[/strike]. When using an array with pointers, every time a new TileChunk needs to be accessed, it needs to be pulled into the cache from somewhere else.

How much slower it is depends on how the TileChunks are stored, and if the ones needed happen to reside in a higher level cache.

There's nothing wrong doing it your way, and you can always go back to it later if it becomes a problem. Profilers are pretty good these days!

Edit: I didn't read the code properly. The strikethrough part isn't true since chained chunks are stored in a separate memory arena.
Kim
Kim Jørgensen
64 posts
Day 55 hash table bug
Thank you for the explanation, jalgelind. I did not consider that the design would impact cache performance, but it makes sense.

/Kim