Skip to main content

Browse the archive

Revision a62f9d1ace8c6556cbc1bb7df69eff0a0bb9e774 authored by Garima Singh on 04 September 2019, 17:36:39 UTC, committed by Johannes Schindelin on 05 December 2019, 14:36:40 UTC 
test-path-utils: offer to run a protectNTFS/protectHFS benchmark
 
In preparation to flipping the default on `core.protectNTFS`, let's have
some way to measure the speed impact of this config setting reliably
(and for comparison, the `core.protectHFS` config setting).

For now, this is a manual performance benchmark:

	./t/helper/test-path-utils protect_ntfs_hfs [arguments...]

where the arguments are an optional number of file names to test with,
optionally followed by minimum and maximum length of the random file
names. The default values are one million, 3 and 20, respectively.

Just like `sqrti()` in `bisect.c`, we introduce a very simple function
to approximation the square root of a given value, in order to avoid
having to introduce the first user of `<math.h>` in Git's source code.

Note: this is _not_ implemented as a Unix shell script in t/perf/
because we really care about _very_ precise timings here, and Unix shell
scripts are simply unsuited for precise and consistent benchmarking.

Signed-off-by: Garima Singh <garima.singh@microsoft.com>
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
1 parent 525e7fb
Raw File
prio-queue.c 
#include "cache.h"
#include "prio-queue.h"

static inline int compare(struct prio_queue *queue, int i, int j)
{
	int cmp = queue->compare(queue->array[i].data, queue->array[j].data,
				 queue->cb_data);
	if (!cmp)
		cmp = queue->array[i].ctr - queue->array[j].ctr;
	return cmp;
}

static inline void swap(struct prio_queue *queue, int i, int j)
{
	SWAP(queue->array[i], queue->array[j]);
}

void prio_queue_reverse(struct prio_queue *queue)
{
	int i, j;

	if (queue->compare != NULL)
		die("BUG: prio_queue_reverse() on non-LIFO queue");
	for (i = 0; i < (j = (queue->nr - 1) - i); i++)
		swap(queue, i, j);
}

void clear_prio_queue(struct prio_queue *queue)
{
	FREE_AND_NULL(queue->array);
	queue->nr = 0;
	queue->alloc = 0;
	queue->insertion_ctr = 0;
}

void prio_queue_put(struct prio_queue *queue, void *thing)
{
	int ix, parent;

	/* Append at the end */
	ALLOC_GROW(queue->array, queue->nr + 1, queue->alloc);
	queue->array[queue->nr].ctr = queue->insertion_ctr++;
	queue->array[queue->nr].data = thing;
	queue->nr++;
	if (!queue->compare)
		return; /* LIFO */

	/* Bubble up the new one */
	for (ix = queue->nr - 1; ix; ix = parent) {
		parent = (ix - 1) / 2;
		if (compare(queue, parent, ix) <= 0)
			break;

		swap(queue, parent, ix);
	}
}

void *prio_queue_get(struct prio_queue *queue)
{
	void *result;
	int ix, child;

	if (!queue->nr)
		return NULL;
	if (!queue->compare)
		return queue->array[--queue->nr].data; /* LIFO */

	result = queue->array[0].data;
	if (!--queue->nr)
		return result;

	queue->array[0] = queue->array[queue->nr];

	/* Push down the one at the root */
	for (ix = 0; ix * 2 + 1 < queue->nr; ix = child) {
		child = ix * 2 + 1; /* left */
		if (child + 1 < queue->nr &&
		    compare(queue, child, child + 1) >= 0)
			child++; /* use right child */

		if (compare(queue, ix, child) <= 0)
			break;

		swap(queue, child, ix);
	}
	return result;
}
back to top