Re: [PATCH v2 4/6] pack-bitmap: prepare to read lookup table

[Abhradeep Chakraborty <chakrabortyabhradeep79@gmail.com>]

Taylor Blau <me@ttaylorr.com> wrote:

> ...exactly my thoughts, too. It's possible that it would be faster to
> key this search on the object_id "oid" above, and then convert each of
> the entries in the lookup table from a uint32_t into an object_id by
> calling nth_bitmap_object_oid() repeatedly.
>
> I *think* that what Abhradeep wrote here is going to be faster more
> often than not since it makes more efficient use of the page cache
> rather than switching between reads across different memory mapped
> regions at each point in the binary search.
>
> But of course that depends on a number of factors. Abhradeep: if you're
> up for it, I think it would be worth trying it both ways and seeing if
> one produces a meaningful speed-up or slow-down over the other. Like I
> said: my guess is that what you have now will be faster, but I don't
> have a clear sense that that is true without trying it both ways ;-).

Ok. Let me try both the ways. In my opinion, I think my version has
less searching and less computation. So, I want to stick with this
version. But I also like to try the other one once so that we can
get the best out of these two.

> I think starting off with a small array and then letting it grow
> according to alloc_nr() would be fine here, since it will grow more and
> more each time, so the amount of times we have to reallocate the buffer
> will tail off over time.

What should be the size of that array?

> If we were really concerned about it, we could treat the buffer as a
> static pointer and reuse it over time (making sure to clear out the
> portions of it we're going to reuse, or otherwise ensuring that we don't
> read old data). But I doubt it matters much either way in practice: the
> individual records are small (at just 4 bytes each) and entry_count is
> often less than 1,000, so I think this probably has a vanishingly small
> impact.

Before submitting it to the mailing list, I did use the ALLOC_GROW macro
function. But my version was worse than yours. For every iteration I was
reallocating the array to support `size+1` positions. But later I drop
the code as this might be very much expensive.

Then I wrote this code. As `table` array and `table_inv` array allocate
this size of arrays (though all the indices are used), I thought it
would not be a problem if I use an array of this size for a small amount
of time.

Honestly, I don't like to realloc arrays. Because as far as I can remember,
realloc allocates a new array internally and copies the items from the old
array to the new array. This irritates me.

But at the same time, it is also true that in most cases we might not need
this amount of space.

Thanks :)