Re: Is GStringChunk still useful?

[mark mark mielke cc]

On Mon, Nov 06, 2006 at 09:30:17PM -0600, Hans Petter Jansson wrote:
> On Mon, 2006-11-06 at 22:28 -0500, mark mark mielke cc wrote:
> > On Mon, Nov 06, 2006 at 08:55:49PM -0600, Hans Petter Jansson wrote:
> > > I seriously doubt that GStringChunk is useful, because the gain from
> > > using non-aligned memory is lost if your strings don't fit the block
> > > size (e.g. too long strings as described by Jeff, or even just the last
> > > block not being completely filled). I'm in favor of obsoleting
> > > GStringChunk.
> > If true, then you should be able to prove it, and nothing is preventing
> > GStringChunk from returning aligned memory.
> > Are you guessing?
> As stated, it depends on the use case.

Did you try it? :-)

Cache lines are often 64 bytes or longer with modern processors.  If
the malloc() header is 16 bytes, and the string is padded to 16 bytes
boundaries, this can mean that a string with length 20 bytes takes up
48 bytes. Two such 20 bytes may be separately allocated on different
pages, leading to a read of 128 bytes or more for two strings. Packed
tightly, 3 x 20 bytes can fit in one 64 byte cache line. Aligned or
un-aligned, reading fewer cache lines is cheaper.

I've recently measured the effect of alignment on Intel Xeon and AMD
X2 processors for string operations (strpcpy() to be exact), and the
effect is only slight.

This is why I suggest that any claims be shown with some sort of
benchmark. The opposite may be true than what was claimed.

> > > We could introduce a function:
> > > g_pack_strings (&mail->from, &mail->to, &mail->cc, &mail->subject,
> > > &mail->body, NULL);
> > > Which would strlen() the strings, allocate a block which would fit the
> > > strings perfectly, copy the strings into the block, free the original
> > > strings and replace the passed-in pointers with the strings' new
> > > locations in the block. The block could be freed thusly:
> > I suspect this would defeat the purpose of using it in the first place.
> > How is mail->from allocated? If using an allocate function, and then
> > re-packing, all you are saving is space. Not allocation time. Space is
> > probably irrelevant in most applications. Allocation time, especially
> > in a multi-threaded context with synchronization on the free memory
> > pools, is not irrelevant.
> That's why I said long-lived. If the data is allocated and kept around
> for a long time, the space saved is more important than the CPU time
> lost.

Long lived doesn't mean frequently accessed. As a long time user of
Perl, and Java, I can say with some certainty that space utilization
is not usually a primary concern.

For multi-threaded applications, however, synchronization is a primary
concern. malloc() has several costs:

    1) Headers - often 16+ bytes (64-bit hardware).

    2) Over allocation - sometimes to next power of 2.

    3) Synchronization - malloc() may be called from multiple threads
       at once, therefore use of the thread pools must be thread safe,
       which requires synchronization. Even with a spin lock, this can
       lead to hardware synchronization of a cache line, meaning a busy
       wait where nothing is actually done for a period.

    4) Locality - allocating two items with malloc() in a row doesn't
       guarantee that they are in the same cache line, let alone on
       the same page of memory.

I was recently looking at GStringChunk for the first time and once I
figured out its real purpose (the documentation is poor) it made
excellent sense to me. There are other projects that use similar
mechanisms. For example, PostgreSQL loads up temporary memory during
the execution of SQL statements, and frees the whole chunk once the
SQL statement is complete. This was intended to solve complex problems
with software that made use of exceptions, where the code would
otherwise contain numerous bugs related to malloc() and free().
Effectively, they are doing a poor man's garbage collector,
where the garbage collection does not occur until the end. It's an
excellent idea in my opinion, and I would suggest that GStringChunk
could be extended to better support this concept. Why only add
strings to the chunk? Why not add data structures, appropriately
aligned?

In C, people use alloca() for similar purposes. alloca() is limited,
however, in that it relies on function boundaries. Using GStringChunk
in a more generic fashion would allow the application to control when
the memory is cleaned up.

Cheers,
mark

-- 
mark mielke cc / markm ncf ca / markm nortel com     __________________________
.  .  _  ._  . .   .__    .  . ._. .__ .   . . .__  | Neighbourhood Coder
|\/| |_| |_| |/    |_     |\/|  |  |_  |   |/  |_   | 
|  | | | | \ | \   |__ .  |  | .|. |__ |__ | \ |__  | Ottawa, Ontario, Canada

  One ring to rule them all, one ring to find them, one ring to bring them all
                       and in the darkness bind them...

                           http://mark.mielke.cc/