From a032f2d84d5584a5d95e8f878cd133a5af5ab2d1 Mon Sep 17 00:00:00 2001
From: Dan Engelbrecht <dan.engelbrecht@epicgames.com>
Date: Tue, 1 Oct 2024 12:38:49 +0200
Subject: optimize gc reference sort (#179)

- Do a single call to mempcy when fetching attachments from the meta store in GC
- Use small lambda when calling std::sort in FilterReferences (enables inlining of the comparision function)
- Use a single function for < and == comparision in KeepUnusedReferences
---
 src/zenstore/gc.cpp | 70 ++++++++++++++++++++++++++++-------------------------
 1 file changed, 37 insertions(+), 33 deletions(-)

(limited to 'src/zenstore/gc.cpp')

diff --git a/src/zenstore/gc.cpp b/src/zenstore/gc.cpp
index 3e0dc5e04..b0a4edf15 100644
--- a/src/zenstore/gc.cpp
+++ b/src/zenstore/gc.cpp
@@ -594,21 +594,23 @@ Sum(GcResult& Stat, bool Cancelled = false)
 }
 
 // For GC the has order only needs to be predictable, it does not have to be "true" sort order
-static inline bool
-LessForGC(const IoHash& Lhs, const IoHash& Rhs)
+static inline int
+CompareForGC(const IoHash& Lhs, const IoHash& Rhs)
 {
 	const uint32_t* LhsData = reinterpret_cast<const uint32_t*>(Lhs.Hash);
 	const uint32_t* RhsData = reinterpret_cast<const uint32_t*>(Rhs.Hash);
 
-	return LhsData[0] < RhsData[0]	  ? true
-		   : LhsData[0] != RhsData[0] ? false
-		   : LhsData[1] < RhsData[1]  ? true
-		   : LhsData[1] != RhsData[1] ? false
-		   : LhsData[2] < RhsData[2]  ? true
-		   : LhsData[2] != RhsData[2] ? false
-		   : LhsData[3] < RhsData[3]  ? true
-		   : LhsData[3] != RhsData[3] ? false
-									  : LhsData[4] < RhsData[4];
+	return LhsData[0] < RhsData[0]	  ? -1
+		   : LhsData[0] != RhsData[0] ? 1
+		   : LhsData[1] < RhsData[1]  ? -1
+		   : LhsData[1] != RhsData[1] ? 1
+		   : LhsData[2] < RhsData[2]  ? -1
+		   : LhsData[2] != RhsData[2] ? 1
+		   : LhsData[3] < RhsData[3]  ? -1
+		   : LhsData[3] != RhsData[3] ? 1
+		   : LhsData[4] < RhsData[4]  ? -1
+		   : LhsData[4] != RhsData[4] ? 1
+									  : 0;
 }
 
 bool
@@ -649,7 +651,9 @@ FilterReferences(GcCtx& Ctx, std::string_view Context, std::vector<IoHash>& InOu
 	{
 		return false;
 	}
-	std::sort(InOutReferences.begin(), InOutReferences.end(), LessForGC);
+	std::sort(InOutReferences.begin(), InOutReferences.end(), [](const IoHash& Lhs, const IoHash& Rhs) {
+		return CompareForGC(Lhs, Rhs) < 0;
+	});
 	auto NewEnd = std::unique(InOutReferences.begin(), InOutReferences.end());
 	InOutReferences.erase(NewEnd, InOutReferences.end());
 	return true;
@@ -676,28 +680,28 @@ KeepUnusedReferences(std::span<const IoHash> SortedUsedReferences, std::span<IoH
 
 	while (ReferencesRead != ReferencesEnd && UsedReferencesRead != UsedReferencesReadEnd)
 	{
-		const IoHash& Reference		= *ReferencesRead;
-		const IoHash& UsedReference = *UsedReferencesRead;
-		if (Reference == UsedReference)
-		{
-			// Skip it
-			ReferencesRead++;
-			UsedReferencesRead++;
-		}
-		else if (LessForGC(Reference, UsedReference))
-		{
-			// Keep it
-			if (ReferencesRead > ReferencesWrite)
-			{
-				*ReferencesWrite = Reference;
-			}
-			ReferencesWrite++;
-			ReferencesRead++;
-		}
-		else
+		switch (CompareForGC(*ReferencesRead, *UsedReferencesRead))
 		{
-			// Skip it
-			UsedReferencesRead++;
+			case 0:
+				// Skip it
+				ReferencesRead++;
+				UsedReferencesRead++;
+				break;
+			case -1:
+				// Keep it
+				if (ReferencesRead > ReferencesWrite)
+				{
+					*ReferencesWrite = *ReferencesRead;
+				}
+				ReferencesWrite++;
+				ReferencesRead++;
+				break;
+			case 1:
+				UsedReferencesRead++;
+				break;
+			default:
+				ZEN_ASSERT(false);
+				break;
 		}
 	}
 
-- 
cgit v1.2.3