Re: same-address mappings vs. relative pointers

On 2013-12-05 10:17:18 -0500, Robert Haas wrote:
> On Thu, Dec 5, 2013 at 9:44 AM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> >> Why? Lots of people have written lots of programs that do just that.
> >
> > Well, but we're a database, not a generic programming library ;)
>
> I think we're arguably both.

Fair enough.

> I don't know if you've noticed, but the overhead of palloc is pretty
> much insane for large memory contexts right now.

Yea, I have more than noticed. I actually still have a partial
replacement of aset.c lying around. It didn't even have 16bytes
overhead, although that had required some ugly hacks when wanting to
continue allowing several parallel context implementations.

Btw, it's even worse if you have lots of allocations above
ALLOC_CHUNK_LIMIT, we walk a linear list on reset, and we reset damn
frequently - partially because we think it's cheap.

> Consider a bunch of
> 100-byte tuples that you want to sort, on a 64-bit machine. IIUC,
> we're going to round the request up to 128 bytes and then add 16 bytes
> of overhead for 2 pointers before the beginning of the chunk.

I think we add the 16bytes overhead before rounding up, but I might
misremember.

> That's
> 44% overhead. For small memory contexts like the ones that store
> syscache entries it's really hard to do any better, but there are much
> better algorithms (which I am investigating) for cases where you
> expect to allocate a large amount of memory.

What I was working on was a slab allocator where, in addition to default
sizes like the current ones, you could create specific slabs for certain
sizes one knew would be frequently be used which then would a) be faster
to allocate b) have lower space overhead c) were guaranteed not to cause
fragmentation.

While I agree that the memory consumption is one concern, I am more
worried about the time it eats up in many workloads.

> > So, for a) what if we, instead of storing plain offsets have something like:
> > typedef struct sptr
> > {
> > Offset sptr_self;
> > Offset sptr_offset;
> > } sptr;
>
> I like the name Offset, but I'm firmly convinced that a relative
> pointer needs to be the same size as a regular pointer. 8 bytes for a
> pointer is already painfully large in some contexts; 16 is just too
> much.

I don't find that all that convincing. In 90% of the cases only a few
pointers will be needed, for those something like the above will be
helpful, allow bounds checking and all. For the 10% of other cases, we
can still open-code stuff. Quite possibly we would want to avoid using
8 bytes there anyway.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services