[PATCH 08 of 10 V2] sparse-revlog: introduce native (C) implementation of slicechunktodensity

[Yuya Nishihara]

On Thu, 15 Nov 2018 11:38:46 +0100, Boris Feld wrote:
> # HG changeset patch
> # User Boris Feld <boris.feld at octobus.net>
> # Date 1542276598 -3600
> #      Thu Nov 15 11:09:58 2018 +0100
> # Node ID 465af090febebc1c8ca8e402c279349ccd09e091
> # Parent  f76fc4ed86fd2072c861f57a3c1c3e892648fc92
> # EXP-Topic sparse-perf
> # Available At https://bitbucket.org/octobus/mercurial-devel/
> #              hg pull https://bitbucket.org/octobus/mercurial-devel/ -r 465af090febe
> sparse-revlog: introduce native (C) implementation of slicechunktodensity
> 
> This is a C implementation of `_slicechunktodensity` in the
> `mercurial/revlogutils/deltas.py` file.
> 
> The algorithm involves a lot of integer manipulation and low-level access to
> index data. Having a C implementation of it raises a large performance
> improvement. See later changeset in this series for details.
> 
> diff --git a/mercurial/cext/revlog.c b/mercurial/cext/revlog.c
> --- a/mercurial/cext/revlog.c
> +++ b/mercurial/cext/revlog.c
> @@ -11,6 +11,7 @@
>  #include <assert.h>
>  #include <ctype.h>
>  #include <stddef.h>
> +#include <stdlib.h>
>  #include <string.h>
>  
>  #include "bitmanipulation.h"
> @@ -1050,6 +1051,210 @@ static PyObject *_trimchunk(indexObject 
>  	return chunk;
>  }
>  
> +struct Gap {
> +	Py_ssize_t size;
> +	Py_ssize_t idx;
> +};
> +
> +static int gap_compare(const void *left, const void *right)
> +{
> +	const struct Gap *_left = ((const struct Gap *)left);
> +	const struct Gap *_right = ((const struct Gap *)right);
> +	if (_left->size < _right->size) {
> +		return -1;
> +	} else if (_left->size > _right->size) {
> +		return 1;
> +	}
> +	return 0;
> +}
> +static int Py_ssize_t_compare(const void *left, const void *right)
> +{
> +	const Py_ssize_t _left = *(const Py_ssize_t *)left;
> +	const Py_ssize_t _right = *(const Py_ssize_t *)right;
> +	if (_left < _right) {
> +		return -1;
> +	} else if (_left > _right) {
> +		return 1;
> +	}
> +	return 0;

Nit: IIRC, names starting with _ is reserved for compilers. Better to not
use such variables.

> +static PyObject *index_slicechunktodensity(indexObject *self, PyObject *args)
> +{
> +	/* method arguments */
> +	PyObject *list_revs = NULL; /* revisions in the chain */
> +	double targetdensity = 0.5; /* min density to achieve */
> +	Py_ssize_t mingapsize = 0;  /* threshold to ignore gaps */

Nit: perhaps these default values, 0.5 and 0, wouldn't be used since function
arguments aren't optional.

This patch looks good to me.

As a follow up, can you somehow rewrite the doctests in deltas.py to run with
the C implementation? Since _testrevlog() isn't backed by the index object,
C functions aren't covered by the doctests. That's unfortunate.