Memory, IPC. Tradeoffs.

I've been playing around with a few ideas for libeze but it's not gotten anywhere particular yet. I'm getting stuck on the tradeoffs - even though they don't really matter much.

IPC - Serialisation

It started when I read a rant against serialsiation formats; this I agree with. An internal blob isn't that important but I thought i'd look at some to see if any where useful.

XDR

This is old and simple. It was written by a smart bunch from a smart company from a time when smarter decisions were being made about things like this. The biggest drawback is the big-endian nature, but I could always fudge it and just pass native-endian values and call it RDX or something.

I then had the bright idea of being able to decode structures without any additional memory - merely referencing the packet data. But this creates a couple of additional areas where it would diverge: strings would need to include their trailing nul byte to be useful, and embedded arrays might need specific alignment.

So really, it's not quite RFX anymore either. OTOH R is listed as `supporting' XDR but it's version is modified as well.

XDR is also not self describing but descriminated descriminated unions go a long way to handling versioning which is the main reason I might want such a feature.

ASN.1 BER/DER/CER/PER

There is actually some stuff I quite like about BER. It's self describing and relatively compact.

There's a lot that makes it a pain. A full implementation needs to implement a lot as it is vastly over-engineered; this means it is complex and likely to be buggy. REAL numbers are encoded in a way that needs a lot of fiddling about on either end.

It's not all wrong, but it's not too right either.

Protocol buffers

I've had the misfortune to have to deal with these for work.

The actual on-wire format isn't too bad. It's not self-describing but you can safely skip buts you don't understand. It's relatively compact. It's also a bit pointless.

The SDK is a complete pile of shit though. The Java implementation compiles gigantic code that runs fucking slow (List<Float>???). It moves all of the protocol variance decisions into the calling code so it's a messy pain to use as well: sort of negating one of the reasons to use a self-describing format in the first place.

For work I wrote my own decoder when I could - a couple of dozen lines of code. But some projects use such complex structures you end up with a gigantic library to decode it (supplied by protoc) and then a gigantic library to marshall it's output into something usable (that you write by hand).

JSON

It's just fucked. Even the same implementation can't decide how to canonically encode empty or single-element arrays, null or emptry strings, and so on.

It's not very compact and while it's realtively simple to parse it's not trivial either.

And then it's clumsy as fuck to use from any non-dynamic language. Getting fields you even know are there is a pain. Handling variances is worse.

CBOR (and half a dozen others)

Well this is just binary JSON. It fixes the end-to-end canonical encodingness and is arguably faster to parse but it's still going to be clumsy to use and not significnatly more compact except for arrays of small integers.

It also has some questionable design decisions and is already bloating with a dozen extension types - it seems like it wants to look as 'valid' as ASN.1/BER but with an even messier encoding scheme.

The whole "look we have a completely-defined 256 element jump table" is just a fucking weird thing to have in a serialisation format RFC. And nothing says simple like 256 right? What on earth is that even about?

SDXF

This is another RFC I came across along the way - not sure how as it just took me 10 minutes to re-find it.

Honestly it's a weird arsed format that looks like someone's internal stuff they decided to publish. I can't imagine anyone uses it.

I would note that with some small changes the meta-data I have can support pretty much all of these formats.

But I pretty much wasted a few hours of my life on this. After all that fucking around I would be inclined to just dump structures around if i didn't need strings! I have several desirable features which can't be covered by a single format anyway, although two would probably suffice.

e.g. here's some use cases.

• Persistent storage.
  • Compact
  • Fast decoding
  • Versionable
  • Objects are good enough to be used directly without having a DTO
  • Complex and nested structures?
  • Self describing?
• Local IPC
  • Very fast encoding and decoding
  • Possibility to decode without auxilliary memory
  • Simple and flat structures
  • Keep security in mind
• Internet IPC, External interfaces.
  • Compact
  • Versionable
  • Possibly to encode and decode in a streaming fashion
  • Simple and unambiguous to help avoid writing-in security issues
  • Self describing?

Ok, maybe 3 formats. Although i'm not really interested in the 3rd at the moment.

The Local IPC case is basically a subset of XDR, aside from the aforementioned tweaks.

The rest? Plenty there but none are a great fit.

Memory

Memory allocation in C is simple enough but managing it can be a bit of a pain, hence pools.

Another issue is that a given implementation enforces certain constraints which can waste (significant) memory: for example on an amd64 platform, malloc() allocates at least 32-bytes for each allocation even if it's only a 5 byte string (this is is the minimum required to track free blocks). And every allocation also saves a size_t before the memory block so it knows how big it was when you call free: when you have many small objects of the same size this wastes a lot of memory. A more subtle problem is that memalign() must also save this size, so that if you start allocating many aligned structures you start to quickly get a holey memory.

Dealing with strings in general is a bit of a pain (and a source of many security issues) and only the GNU-sepcific obstack really provides any good support for it.

So I experimented with a few ideas.

High level internals of malloc() & free()

An implementation of this pair basically all work the same.

malloc will find a block of free memory big enough to hold the requested size plus space to hold that size. Some area of this block will be reserved for the allocation and the free block will either be reduced by the same amount, or removed (if the whole block is used).

free() will take the saved size and address and mark it as free. As part of this process it will find out if there are other free blocks immediately adjacent to this new free block and coalesce them into a single larger block if so. There are only 4 cases: isolated free, adjacent before, adjacent after, adjacent before and after.

The memory in the free block itself is used to hold the controlling structures required for the two functions. They cease to exist once the memory is allocated.

Additionally, for finding blocks there are two basic strategies:

first-fit

The free list is stored sorted by address. It is scanned from the start and the first block with enough memory to fit the request is used.

best-fit

The free list is sorted by size. It is scanned from a block which is larger-or-equal to the desired size and the first one is used.

Each has their benefits and trade-offs.

first-fit may be slower to allocate but will more effectively utilise memory - less total memory will be required. I did some basic and non-exhaustive testing that gave me this result. It can also be implemented with very simple code and the same list can be used for performing coalescing.

best-fit can be faster to allocate as you find the correct block directly. Based on my testing it requires more total memory. Additional data structures are required to implement the free() operation.

So finally, these choices any other indices arequired determine the data structures required to track and find the free blocks, and thus determine the minimum allocation size.

GNU libc malloc() uses a size_t for the block size, a double-linked list for the free list, and another size_t at the end of the free block for fast coalescing. So the minimum size of a free block (and hence the minimum allocation size) is 32 bytes on a 64-bit system 16 bytes on a 32-bit system. I think it uses best-fit.

AllocMem()/FreeMem()

The first memory allocator I knew was the one from AmigaOS via AllocMem(). This only has a single constraint in that the minimum allocation is 8 bytes. There is no fixed allocation overhead to store the allocated size as you need to also provide the size to FreeMem(). Free nodes are stored as a single-linked list.

It takes very little code to implement this and it utilises memory very well (it can't really be more utilised than 100%).

The drawback is that both allocation and deallocation are O(N) operations since both have to walk the free list. I guess 'slow' is relative as they did ok on a 7Mhz CPU with a global(!) shared memory list. But because one knew it was slow you wrote code to avoid it (SunOS also had a dreadfully slow allocator so it wasn't unique in this regard).

On memory constrainted systems I think it's still a useful technique. free() can also be accelerated somewhat by using a balanced tree by bumping up the minimum allocation.

ez-page-alloc

So the first idea I played with was a page allocator which would underly more specific algorithms. The idea would be that it would require the free size like FreeMem() and so allow pages to be allocated with no overhead and no wastage.

I didn't really get anywhere with this and then revisited it in a different way later on (ez-alloc-alloc).

ez-string-alloc

I diverted for a little while trying to work on a string allocator. It would take some number of pages as an allocation block. In this case there would be no way to free individual strings. But they wouldn't require any alignment or size overhead either.

Strings can be built a character at a time, and large strings are moved over to their own block.

Allocation can be made very fast by only searching the most recent block. Or it can be made more compact by searching all blocks. Or some trade-off in-between.

I think this could be the basis of a good no-free high performance pool allocator.

On the way I came across apr_pool and it's code is pretty ugly and I was suprised it didn't support free() of individual allocations, given how complex it is.

ez-fixed-alloc

I've written multiple memory allocators in the past and one of the easiest and most useful is an allocator for fixed-sized blocks. It was particularly important for glib container classes.

Free is trivial as you already know the size and never have to coalesce free blocks and you can just plop the memory into the head of a single-linked list.

Allocate is likewise as trivial as a single-linked list.

However you end up having to have multiple allocators for each size so you just end up with a lot of wasted space anyway.

Eh I dunno, i'm thinking about whether this one is useful at all.

ez-alloc-alloc

I had a look at an allocator that could support memalign() without wastage. And basically do-away with a need for a special page allocator.

This is basically a tree-based version of AlocMem()/FreeMem() but with a very large alignment. Because there is no size overhead all memory is used and allocating new page-aligned pages doesn't leave unfillable holes.

Performance problems with the algorithm would be mitigated by having fewer, larger allocations and leaving the internal allocations to other more specific algorithms.

Still I dunno, it's many drawbacks in this form but I like the idea. Probably some sort of external index (radix-tree) would be better and enforcing N*page sized allocations.

ez-pool-alloc

I tried to write an allocator that supported free but with the minimum overhead. I got it down to a minimum allocation size of 8 bytes (void *) with no overhead.

Basically I wrote another AllocMem()/FreeMem() but this time much closer to the original. To support the minimum allocation size of 8 bytes on a 64-bit platform the lsb of the link pointer is used to indicate whether the size is 8 bytes (no room for size) or larger (has size).

This still suffers from the same performance problems, although it can be mitigated by being used only for short-term memory or with few frees.

The Story So Far. A Big Waste Of Fucking Time.

In the end i'm not really sure I like anything I came up with.

I'll probably change the existing ezelib serialiser, and likely split the code up so that the description part is separate from the (multiple) encoding part(s). I'll probably have something XDR-like and another more compact one, maybe tagged. Each may not support all possible structures.

The memory stuff was really just fucking around; I don't remotely need any of this. But I will poke at it some more I guess. Probably a pageish allocator which manages system memory without allocation overhead (at point of allocation), then a couple of allocators which sit atop of it and can be used as pools. A general purpose one and a high-performance non-freeing one that also supports incremental string/structure creation.

The general purpose pool might just end up being very similar to malloc() but with the (rather useful) benefit of being able to be freed en-mass. I can possibly get the minimum allocation size down to 16 bytes although I will need to borrow some bits from ez-tree's ez_node to achieve this. I can possibly also get first-fit to work efficiently (order tree by size then address?). I think i'm going to have to save the size in allocations though (thus 8-byte allocation overhead): it's going to be needed a lot of the time and I can't do fast coalescing without it. If I have a particualrly fast page allocator i might be able to do something neat for small fixed-sized allocs and that would also cover the interesting memalign cases.

Ultumately they would also need valgrind instrumentation as well.

Probably back to work next week, should get away from the screen. Wheather's nice and warm but not too hot. Finally getting a few tomatoes and the sweet-corn is nearly there.