Re: [PATCH] describe: rewrite name_rev() iteratively

From: Jeff King <peff@peff.net>
Date: Apr 8, 2014, 18:50 UTC
Message-ID: <20140408185047.GA7073@sigill.intra.peff.net>
In-Reply-To: <1396824434-31672-1-git-send-email-dragos.foianu@gmail.com>

On Mon, Apr 07, 2014 at 01:47:14AM +0300, Dragos Foianu wrote:

Show 7 quoted lines

> The "git describe --contains" command uses the name_rev() function which
> is currently a recursive function. This causes a Stack Overflow when the
> history is large enough.
> 
> Rewrite name_rev iteratively using a stack on the heap. This slightly
> reduces performance due to the extra operations on the heap, but the
> function no longer overflows the stack.

You can avoid the heap overhead by using an array for your stack, and only resizing it when necessary. Like this:

    struct rev_stack {
            int nr, alloc;
            struct rev_data *data;
    };

    static struct rev_data *rev_stack_push(struct rev_stack *stack)
    {
            ALLOC_GROW(stack->data, stack->nr + 1, stack->alloc);
            return &stack->data[stack->nr++];
    }

    static void rev_stack_pop(struct rev_stack *stack)
    {
            stack->nr--;
    }

    static void rev_stack_init(struct rev_stack *stack)
    {
            stack->nr = stack->alloc = 0;
            stack->data = NULL;
    }

    static void rev_stack_release(struct rev_stack *stack)
    {
            free(stack->data);
            rev_stack_init(stack);
    }

Usage would be something like:

    struct rev_data *data = rev_stack_push(&stack);
    data->commit = commit;
    data->tip_name = tip_name;
    ...

IOW, you push first to allocate the space, and then do your make_rev_data, rather than the other way around.

The downside is that your allocation is always as big as the deepest recursion so far, so you hold on to the memory a little longer than necessary. I think that's a good tradeoff versus an extra malloc() for every commit.

-Peff