Saturday, December 31, 2016

set, match, meta operator

The common set operations; difference, join/intersect and union; may all be efficiently implemented on top of a meta operator that I've come to call 'match'. It does what it says: finds the next matching element, given two sets. The following examples are from libc4life's binary sets, but the idea is universally applicable.

the match operator



set operations


Once match is given, the actual operations read like poetry. For brevity, only join/intersect is included here; remaining operations vary only in the way they deal with matches/gaps.


Besides simplifying the implementation, exposing the underlying mechanism like this also gives user code a second chance for optimized access when provided operations don't fit the problem.

peace, out

Friday, December 30, 2016

partial STM for C structs

c4life provides partial STM support for changes made to records, partial meaning single threaded. Transactions are useful in many single threaded scenarios; and layering the rest of a multi threaded implementation on top as a separate abstraction is perfectly doable, should one be so inclined. Transactions may be rolled back and/or committed several times during their life; rolling back resets all logged records to their last logged values, and committing resets the transaction. Records may be logged in any transaction; and are automatically logged in the last started, active transaction; if any; when added to tables.


peace, out

Sunday, December 25, 2016

Lispy sets

I've been playing around with adding ordered sets to Common Lisp lately. I started out by pulling my usual tricks, skip lists and binary searched/dynamically grown vectors; but none of them turned out the way I wanted; I always had the feeling I was fighting the language rather than enjoying the ride, which is unusual.

So I turned a new page; took a deep breath; and brain dumped the most naive, workable solution I could think of. Like Lisp's built in sets; slists store their items as lists, with the difference that they're sorted and keep track of length and tail. This allows them to implement ordering and more in 200 lines of reasonable code; while being significantly (currently hovering above 10x) faster than built in (as in SBCL) functionality for set operations. Once again, keeping it simple proves to be a successful strategy.


And here is the benchmark on which I base these outrageous claims, and a print out from my machine:



A full implementation of these ideas and more may be found here.

peace, out

Thursday, December 22, 2016

first class, composite key indexes

There comes a point in many projects where there is a choice between adding yet another layer of maps of arrays and pulling in a serious database engine, many fail to stop and consider other available options. Arrays and maps are not the end of the story when it comes to data structures, there are more powerful general purpose abstractions available.

libc4life provides ordered composite key indexes with user specified key and value types and value semantics, based on binary searched maps. Indexes are optionally unique and/or hashed. Hashed indexes are ordered within slots and allow overriding the algorithm for assigning slots to keys.


peace, out

Wednesday, December 21, 2016

faster strcmp

This is a reminder about a nice technique for speeding up string comparisons. Some will call this cheating, as we'll be doing some work up front and trade space for speed; but the technique is useful in many common scenarios where most default to plain old strcmp.

libc4life provides ordered symbol tables based on binary searched sets. A symbol is simply a pointer to it's index in the set; this means it might change when more symbols are added, but the relative ordering stays the same. To speed up table generation, symbol names are const referenced instead of copied.


peace, out

Monday, December 19, 2016

assertions done right

The problem with using assertions to sanity check code with side effects is the hidden dependency on compiler switches, not the idea in itself. libc4life provides a custom set of assert macros that solves the problem. The basic macro evaluates the expression once for side effects, and injects the result into the specified condition; which is finally asserted. Turning off assertions still evaluates expressions for side effects, and errors are thrown out of band to make sure failures are detected. As an added bonus; the macros return the result of evaulating the expression, which means they can take part in longer expressions. Implementation is trivial; but considering it took me 30 years to get a round tuit, maybe posting this can help someone short circuit their process.


peace, out

Saturday, December 17, 2016

basic C macros

Macros in C generally have a bad reputation that's based on mostly obsolete or incorrect information, this post is an attempt at shining some light into that corner.

code blocks

Passing code blocks as macro parameters is useful for splicing user defined code into a template and returning the result. libc4life's 'C4LAMBDA' uses the technique to define a nested function and return it's address in one statement.


repeated side effects

One of the more popular objections to C macros is the risk of repeatedly evaluating code with side effects. This risk is not unique to C; it comes with the basic capability to paste the same code repeatedly. In many cases it's possible to get around the issue by declaring temporary variables to hold the result of evaluating parameters once. libc4life uses that technique to implement a safe MAX macro.


identifiers

libc4life provides macros for appending one identifier to another and for generating unique identifiers.


variable injection

There is nothing wrong with injecting variables into user code, as long as that is the intended outcome. libc4life's provides a macro that allocates memory from the stack and gives the user full control of the pointer when specifying the parameter list for the provided function.


naming conventions

Naming conventions are useful for defining operations on top of protocols with multiple implementations. Most abstractions in libc4life come with an '_init' function, and the library provides a macro to simplify initializing stack allocated memory for any abstraction that implements that protocol.


for loops

The standard for loop comes with additional possibilities to use 'break' and 'continue' as part of the macro's sematics. libc4life uses for loops to implement channel operations that can be aborted by calling 'break'.


code generation

All macros generate code, but some of them deserve being called code generators more than others. libc4life includes a code generator to declare a lazy initialized static variable of user specified type in one statement.


May a thousand macros bloom, and may Source be with you...

peace, out

Friday, December 16, 2016

the malloc challenge - progress update #1

Hi, and welcome to this progress update from the malloc challenge. If you didn't get the original memo, I recommend starting here. Discussions and submissions are directed to the posts on Reddit and Hacker News.

feedback

The challenge got an overwhelming response, leading to many interesting discussions. I'm happy to see that so many are still awake out there, warms my heart.

Some unfortunately missed the point I'm trying to make completely; and got tangled up in giving reasons why writing a system level, general purpose malloc is worse than blindfolded rocket surgery. I know, that is why I think it's about time we put perfect back on the shelf and shift focus to solving specific problems in a good enough, modular, application level framework.

Others were confused by the word 'challenge' and assumed I was announcing a competition, without any prices. Some went on to stroke their egos, before sneaking back into security with arbitrary excuses. This is where competing leads us, constant fight or flight mode where substance is replaced with drama. Even science recognizes we're all part of one whole; you loose, I loose, everyone looses.

benchmark

The benchmark has been updated to use the same random seed for each allocator; to additionally allocate several blocks of the same sizes; and to access the allocated memory, causing access errors for invalid allocations.

interface

Implementation specific freeing functions have been replaced with a 'free' method in the c4malloc interface. 'acquire' has been shortened to 'acq' and 'release' to 'rel'.

allocators

An mmap allocator has been added, it allocates each request using anonymous mmap to avoid malloc's internal book keeping costs. The slab allocator and free list have seen plenty of experimentation with indexing slabs and allocations by size, but finally reverted to using linked lists. Hours of full stack optimization to chisel libc4life's binary set into a viable alternative still resulted in a 300% slowdown, and I can't think of a faster way to do it right now.

performance

The benchmark improvements dissolved most performance oddities, all allocators now exhibit the expected relative performance. The short story is that slab allocation via mmap performs best, significantly better than straight malloc because of reduced number of actual allocations and lack of book keeping; this relation holds when stacking pools or free lists on top.


hope

I still haven't given up hope on external contributions. The repository has seen plenty of forks, but nothing crossed my radar yet. Please share your ideas, however naive or imperfect they may seem to you. This is not a competition, you have nothing to loose and everything to gain.

peace, out