use plain sorted array instead of map of vectors (#237)

* use plain sorted array instead of map of vectors
* reserve vectors up front = 5% perf increase
* don't do batch read of chunks if we have a single chunk -> 1% perf gain

1 files changed, 26 insertions, 18 deletions

diff --git a/src/zenstore/blockstore.cpp b/src/zenstore/blockstore.cpp
index fcf934344..5f2f5cba0 100644
--- a/src/zenstore/blockstore.cpp
+++ b/src/zenstore/blockstore.cpp
@@ -803,7 +803,7 @@ BlockStore::IterateBlock(std::span<const BlockStoreLocation>   ChunkLocations,
 
 			const size_t BlockSize	= BlockFile->FileSize();
 			const size_t RangeCount = GetNextRange(BlockSize, ChunkIndexes, LocationIndexOffset);
-			if (RangeCount > 0)
+			if (RangeCount > 1)
 			{
 				size_t					  LastChunkIndex = ChunkIndexes[LocationIndexOffset + RangeCount - 1];
 				const BlockStoreLocation& LastLocation	 = ChunkLocations[LastChunkIndex];
@@ -870,31 +870,39 @@ BlockStore::IterateChunks(const std::span<const BlockStoreLocation>& ChunkLocati
 
 	ZEN_LOG_SCOPE("iterating chunks from '{}'", m_BlocksBasePath);
 
-	tsl::robin_map<uint32_t, size_t> BlockIndexToBlockChunks;
-	std::vector<std::vector<size_t>> BlocksChunks;
-
+	std::vector<size_t> ChunkOrder(ChunkLocations.size());
 	for (size_t ChunkIndex = 0; ChunkIndex < ChunkLocations.size(); ++ChunkIndex)
 	{
-		const BlockStoreLocation& Location = ChunkLocations[ChunkIndex];
-		if (auto It = BlockIndexToBlockChunks.find(Location.BlockIndex); It != BlockIndexToBlockChunks.end())
-		{
-			BlocksChunks[It->second].push_back(ChunkIndex);
-		}
-		else
-		{
-			BlockIndexToBlockChunks.insert(std::make_pair(Location.BlockIndex, BlocksChunks.size()));
-			BlocksChunks.push_back(std::vector<size_t>({ChunkIndex}));
-		}
+		ChunkOrder[ChunkIndex] = ChunkIndex;
 	}
 
-	for (auto& BlockChunks : BlocksChunks)
+	std::sort(ChunkOrder.begin(), ChunkOrder.end(), [&ChunkLocations](const size_t Lhs, const size_t Rhs) {
+		return ChunkLocations[Lhs].BlockIndex < ChunkLocations[Rhs].BlockIndex;
+	});
+	size_t					RangeStart = 0;
+	size_t					RangeEnd   = 0;
+	const std::span<size_t> ChunkIndexRange(ChunkOrder);
+	while (RangeStart < ChunkOrder.size())
 	{
-		ZEN_ASSERT(!BlockChunks.empty());
-		uint32_t BlockIndex = ChunkLocations[BlockChunks[0]].BlockIndex;
-		if (!Callback(BlockIndex, BlockChunks))
+		const size_t   ChunkIndex = ChunkOrder[RangeStart];
+		const uint32_t BlockIndex = ChunkLocations[ChunkIndex].BlockIndex;
+		RangeEnd++;
+		while (RangeEnd < ChunkOrder.size())
+		{
+			const size_t NextChunkIndex = ChunkOrder[RangeEnd];
+			if (ChunkLocations[NextChunkIndex].BlockIndex != BlockIndex)
+			{
+				break;
+			}
+			++RangeEnd;
+		}
+
+		if (!Callback(BlockIndex, ChunkIndexRange.subspan(RangeStart, RangeEnd - RangeStart)))
 		{
 			return false;
 		}
+
+		RangeStart = RangeEnd;
 	}
 	return true;
 }