diff mbox series

[v5,4/5] pack-redundant: consistent sort method

Message ID 20190110120142.22271-5-worldhello.net@gmail.com (mailing list archive)
State New, archived
Headers show
Series pack-redundant: new algorithm to find min packs | expand

Commit Message

Jiang Xin Jan. 10, 2019, 12:01 p.m. UTC 
From: Jiang Xin <zhiyou.jx@alibaba-inc.com>

SZEDER reported that test case t5323 has different test result on MacOS.
This is because `cmp_pack_list_reverse` cannot give identical result
when two pack being sorted has the same size of remaining_objects.

Changes to the sorting function will make consistent test result for
t5323.

The new algorithm to find redundant packs is a trade-off to save memory
resources, and the result of it may be different with old one, and may
be not the best result sometimes.  Update t5323 for the new algorithm.

Reported-by: SZEDER Gábor <szeder.dev@gmail.com>
Signed-off-by: Jiang Xin <zhiyou.jx@alibaba-inc.com>
---
 builtin/pack-redundant.c  | 22 +++++++++++++++-------
 t/t5323-pack-redundant.sh |  2 +-
 2 files changed, 16 insertions(+), 8 deletions(-)

Comments

SZEDER Gábor Jan. 10, 2019, 8:05 p.m. UTC | #1 
On Thu, Jan 10, 2019 at 08:01:41PM +0800, Jiang Xin wrote:
> diff --git a/builtin/pack-redundant.c b/builtin/pack-redundant.c
> index 56591d283f..e9d2586e2e 100644
> --- a/builtin/pack-redundant.c
> +++ b/builtin/pack-redundant.c

> @@ -421,16 +422,22 @@ static inline off_t pack_set_bytecount(struct pack_list *pl)
>  	return ret;
>  }
>  
> -static int cmp_pack_list_reverse(const void *a, const void *b)
> +static int cmp_remaining_objects(const void *a, const void *b)
>  {
>  	struct pack_list *pl_a = *((struct pack_list **)a);
>  	struct pack_list *pl_b = *((struct pack_list **)b);
> -	size_t sz_a = pl_a->remaining_objects->size;
> -	size_t sz_b = pl_b->remaining_objects->size;
>  
> -	if (sz_a == sz_b)
> -		return 0;
> -	else if (sz_a < sz_b)
> +	/* if have the same remaining_objects, big pack first */
> +	if (pl_a->remaining_objects->size == pl_b->remaining_objects->size)
> +		if (pl_a->all_objects_size == pl_b->all_objects_size)
> +			return 0;
> +		else if (pl_a->all_objects_size < pl_b->all_objects_size)
> +			return 1;
> +		else
> +			return -1;

My compiler complains about the above nested if statements:

  builtin/pack-redundant.c: In function ‘cmp_remaining_objects’:
  builtin/pack-redundant.c:345:5: error: suggest explicit braces to avoid ambiguous ‘else’ [-Werror=parentheses]
    if (pl_a->remaining_objects->size == pl_b->remaining_objects->size)
       ^
  cc1: all warnings being treated as errors
  Makefile:2302: recipe for target 'builtin/pack-redundant.o' failed

After adding a pair of {} to the outer if statement
't5323-pack-redundant.sh' passed successfully even on macOS (on Travis
CI).
diff mbox series

Patch

diff --git a/builtin/pack-redundant.c b/builtin/pack-redundant.c
index 56591d283f..e9d2586e2e 100644
--- a/builtin/pack-redundant.c
+++ b/builtin/pack-redundant.c
@@ -33,6 +33,7 @@  static struct pack_list {
 	struct packed_git *pack;
 	struct llist *unique_objects;
 	struct llist *remaining_objects;
+	size_t all_objects_size;
 } *local_packs = NULL, *altodb_packs = NULL;
 
 struct pll {
@@ -421,16 +422,22 @@  static inline off_t pack_set_bytecount(struct pack_list *pl)
 	return ret;
 }
 
-static int cmp_pack_list_reverse(const void *a, const void *b)
+static int cmp_remaining_objects(const void *a, const void *b)
 {
 	struct pack_list *pl_a = *((struct pack_list **)a);
 	struct pack_list *pl_b = *((struct pack_list **)b);
-	size_t sz_a = pl_a->remaining_objects->size;
-	size_t sz_b = pl_b->remaining_objects->size;
 
-	if (sz_a == sz_b)
-		return 0;
-	else if (sz_a < sz_b)
+	/* if have the same remaining_objects, big pack first */
+	if (pl_a->remaining_objects->size == pl_b->remaining_objects->size)
+		if (pl_a->all_objects_size == pl_b->all_objects_size)
+			return 0;
+		else if (pl_a->all_objects_size < pl_b->all_objects_size)
+			return 1;
+		else
+			return -1;
+
+	/* sort according to remaining objects, more remaining objects first */
+	if (pl_a->remaining_objects->size < pl_b->remaining_objects->size)
 		return 1;
 	else
 		return -1;
@@ -451,7 +458,7 @@  static void sort_pack_list(struct pack_list **pl)
 	for (n = 0, p = *pl; p; p = p->next)
 		ary[n++] = p;
 
-	QSORT(ary, n, cmp_pack_list_reverse);
+	QSORT(ary, n, cmp_remaining_objects);
 
 	/* link them back again */
 	for (i = 0; i < n - 1; i++)
@@ -593,6 +600,7 @@  static struct pack_list * add_pack(struct packed_git *p)
 		llist_insert_back(l.remaining_objects, (const struct object_id *)(base + off));
 		off += step;
 	}
+	l.all_objects_size = l.remaining_objects->size;
 	/* this list will be pruned in cmp_two_packs later */
 	l.unique_objects = llist_copy(l.remaining_objects);
 	if (p->pack_local)
diff --git a/t/t5323-pack-redundant.sh b/t/t5323-pack-redundant.sh
index 7410426dee..2a09ff1bfb 100755
--- a/t/t5323-pack-redundant.sh
+++ b/t/t5323-pack-redundant.sh
@@ -90,7 +90,7 @@  test_expect_success 'create pack 4, 5' '
 '
 
 cat >expected <<EOF
-P2:$P2
+P3:$P3
 EOF
 
 test_expect_success 'one of pack-2/pack-3 is redundant' '