Re: [PATCH 3/6] object-file: extract logic to approximate object count

[Junio C Hamano <gitster@pobox.com>]

Patrick Steinhardt <ps@pks.im> writes:

>  static int too_many_loose_objects(int limit)
>  {
> ...
> +	int auto_threshold = DIV_ROUND_UP(limit, 256) * 256;
> +	unsigned long loose_count;
> +
> +	if (odb_source_loose_approximate_object_count(the_repository->objects->sources,
> +						      &loose_count) < 0)
>  		return 0;
>  
> -	auto_threshold = DIV_ROUND_UP(limit, 256);
> -	while ((ent = readdir(dir)) != NULL) {
> -		if (strspn(ent->d_name, "0123456789abcdef") != hexsz_loose ||
> -		    ent->d_name[hexsz_loose] != '\0')
> -			continue;
> -		if (++num_loose > auto_threshold) {
> -			needed = 1;
> -			break;
> -		}
> -	}
> -	closedir(dir);
> -	return needed;
> +	return loose_count > auto_threshold;
>  }

We used to sample one shared directory and stopped when we know we
have more than auto_threshold, which is roughly 1/256 of the given
limit.  Now, we ask "approximate" function to count and then compare
the result with the same auto_threshold (i.e., 1/256 of the given
limit), which means we expect approximate function to count only
1/256 of the total loose objects somehow?  Let's keep reading.

>  static struct packed_git *find_base_packs(struct string_list *packs,
> diff --git a/object-file.c b/object-file.c
> index a3ff7f586c..da67e3c9ff 100644
> --- a/object-file.c
> +++ b/object-file.c
> @@ -1868,6 +1868,47 @@ int odb_source_loose_for_each_object(struct odb_source *source,
>  					     NULL, NULL, &data);
>  }
>  
> +int odb_source_loose_approximate_object_count(struct odb_source *source,
> +					      unsigned long *out)
> +{
> +	const unsigned hexsz = source->odb->repo->hash_algo->hexsz - 2;
> +	unsigned long count = 0;
> +	struct dirent *ent;
> +	char *path = NULL;
> +	DIR *dir = NULL;
> +	int ret;
> +
> +	path = xstrfmt("%s/17", source->path);
> +
> +	dir = opendir(path);
> +	if (!dir) {
> +		if (errno == ENOENT) {
> +			*out = 0;
> +			ret = 0;
> +			goto out;
> +		}
> +
> +		ret = error_errno("cannot open object shard '%s'", path);
> +		goto out;
> +	}
> +
> +	while ((ent = readdir(dir)) != NULL) {
> +		if (strspn(ent->d_name, "0123456789abcdef") != hexsz ||
> +		    ent->d_name[hexsz] != '\0')
> +			continue;
> +		count++;
> +	}

This counts one shared ("17" that is randomly picked) fully and then ...

> +	*out = count * 256;

... estimate that the entire world would probably have 256 times as
many as the objects in that one shared.

Ah, my earlier read of the caller was confused.  auto_threshold used
to be 1/256 of the limit, but now the number used is computed in a
strange arithmetic, "DIV_ROUND_UP(limit,256) * 256".  Not directly
using "limit" fooled me into thinking that it somehow kept using the
same 1/256 of the limit.

So we are answering "do we have too many?" question using roughly
the same criteria as before, not 1/256 off as I suspected earlier.

The old implementation exited early as soon as the threshold was
hit.  While scanning a single shard directory is likely fast enough
that this may not matter in practice, it is a slight change in
behaviour. If a repository has an extremely large number of loose
objects (e.g. tens of thousands in shard 17), this will now count
all of them instead of stopping at ~30 (if the limit set to around
7000 objects).

Given that this is an "auto" GC check, the performance difference is
probably negligible, but I thought it worth pointing out.