packed, delta: Some improvements for base selection

* sort objects by type then size to improve window quality
* prune bad candidates with size ratio checks
* have objects are preferred

1 files changed, 50 insertions, 0 deletions

diff --git a/delta_write_select.go b/delta_write_select.go
index 2911867d..db6fc022 100644
--- a/delta_write_select.go
+++ b/delta_write_select.go
@@ -6,9 +6,11 @@ type objectToPack struct {
 	id         Hash
 	ty         ObjectType
 	body       []byte
+	size       int
 	offset     uint64
 	deltaDepth int
 	inPack     bool
+	preferred  bool
 }
 
 type deltaContext struct {
@@ -36,6 +38,8 @@ func pickDeltaBase(ctx *deltaContext, obj *objectToPack, seed uint64, minSavings
 	}
 	var bestBase *objectToPack
 	var bestDelta []byte
+	var bestPreferred *objectToPack
+	var bestPreferredDelta []byte
 	for i := len(ctx.candidates) - 1; i >= 0; i-- {
 		base := ctx.candidates[i]
 		if base.ty != ObjectTypeBlob {
@@ -44,14 +48,60 @@ func pickDeltaBase(ctx *deltaContext, obj *objectToPack, seed uint64, minSavings
 		if base.deltaDepth >= maxDepth {
 			continue
 		}
+		if !deltaSizeOk(base, obj, maxDepth) {
+			continue
+		}
 		delta, ok := deltaTry(base.body, obj.body, seed, minSavings)
+		if base.preferred {
+			delta, ok = deltaTry(base.body, obj.body, seed, 0)
+		}
 		if !ok {
 			continue
 		}
+		if base.preferred {
+			if bestPreferredDelta == nil || len(delta) < len(bestPreferredDelta) {
+				bestPreferredDelta = delta
+				bestPreferred = base
+			}
+			continue
+		}
 		if bestDelta == nil || len(delta) < len(bestDelta) {
 			bestDelta = delta
 			bestBase = base
 		}
 	}
+	if bestPreferred != nil {
+		return bestPreferred, bestPreferredDelta
+	}
 	return bestBase, bestDelta
 }
+
+func deltaSizeOk(base, target *objectToPack, maxDepth int) bool {
+	if base == nil || target == nil {
+		return false
+	}
+	if base.size <= 0 || target.size <= 0 {
+		return false
+	}
+	if maxDepth <= 0 {
+		maxDepth = 1
+	}
+	if base.deltaDepth >= maxDepth {
+		return false
+	}
+	if target.size < base.size/32 {
+		return false
+	}
+	maxSize := target.size/2 - 32
+	if maxSize <= 0 {
+		return false
+	}
+	sizediff := 0
+	if base.size < target.size {
+		sizediff = target.size - base.size
+	}
+	if sizediff >= maxSize {
+		return false
+	}
+	return true
+}