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

[Boris FELD]

On 16/11/2018 14:40, Yuya Nishihara wrote:
> 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.
Oops, fixed.
>
>> +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.
I updated the code to set them both to 0. Should we leave them
non-initialized?
>
> 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.
That won't be easy, the doctest use a mock python class to emulate the
revlog. On the other hand, the C code expects the real object.
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel at mercurial-scm.org
> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel