It would be better to use an array of pointers instead, to avoid the need for checking the X value
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
- Casey
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:
with this:
should fix the problem.
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.
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.
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).
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).
Edited by Fredrik Forsberg
on
Reason: typo
You're right !
I should have step through the code to check what I was thinking. I'll do that next time. Thanks
I should have step through the code to check what I was thinking. I'll do that next time. Thanks
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
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
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:
/Kim
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
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.
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.
Edited by Johannes Algelind
on
Reason: I can't read.
Thank you for the explanation, jalgelind. I did not consider that the design would impact cache performance, but it makes sense.
/Kim
/Kim