Quite some time ago I posted a memory allocator on sumea. It became the core of a much larger library I've been working on. Sumeans may well find it usefull, and you can use it in commercial projects without having to pay me anything [;)]
It's only in subversion as yet, and the build instructions are outdated (but just use the msvc project file). I'm working on it...
http://sourceforge.net/projects/ldk
the code can be viewed at http://svn.sourceforge.net/viewcvs.cgi/ldk/trunk/
and checked out anonymously with the command
svn co https://svn.sourceforge.net/svnroot/ldk/trunk ldk
Here's a description and (incomplete) feature list
A 64-bit clean (hopefully!), portable, object oriented library of tightly integrated low-level classes, templates and functions targetting realtime multithreaded applications such as midi sequencers and audio synthesisers. Likely to be useful for next-gen game and simulation engines. It has been designed to be the base of a real-time audio synthesis scripting language.
Features include
- Thread local storage.
- Global and thread-local generic Singleton classes.
- A very fast, flexible, low latency (soft-RTOS) and quite reasonably resource conservative thread local memory pool based generic allocatotion system which takes advantage of the compilers' innate knowledge of the size of types to shift some of the allocation load to compile time.
- Custom STL memory allocator templates that take partial (run-time only) advantage of the allocation system.
- Debug build memory leak tracking that reports filename and line number of each leaked allocation.
- Several reference counted smart pointers (intrusive and non-intrusive).
- Multiple accurate, reapeatable and pausable timers with variable tick times.
- Thread local scheduling and co-operative multitasking.
- Thread, Mutex and Lock classes.
- A basic lockless queue template for low latency inter-thread communication.
- Object oriented filesystem virtualisation able to read from zip files and numerous game formats (via an enhanced wrapping of physfs). Also supports transparent on-read translation of windows text files on unix systems ans vice/vera. Provides per-thread re-directable stdio.
- A templated Hash table (with a partial specialisation for const char pointers).
- XML reading, parsing and writing (via a hacked TinyXml).
- Template based XML object serialisation (via a hacked TinyBind).
- Exception based error reporting.
- Liberal use of the assert macro throughout.
- Uses an advanced, easily extendible build system (scons, build scripts are in python) with short, clearly separated build scripts for each platform.
- The beginnings of a regression test suite. The included tests indicate the core of the library is highly functional.
- Extremely friendly license (zlib)
- Doxygen documentation
Planned future features include UTF-8 (unicode) and plugin support.
LDK has been known to compile and work with:
- GNU G++ 3.x on x86-64 GNU-Linux.
- GNU G++ 4.x on x86 GNU-Linux.
- GNU G++ 3.x on x86 GNU-Linux.
- Intel C++ 8.0 on x86 GNU-Linux.
- MinGW G++ 3.x
- MSVC.net 2003
[*]MSVC.net 2005
[*]Intel C++ 8.0 on win32.
I was browsing through the source, and was curious of a few things...
For your containers, why not use std style syntax (lower_case) so that you can use them with algorithms? Seems an awful lot to miss out on if you are going to write a good hash container to not be able to use it with all standard code or templates expecting models of standard Concepts.
Nice to see the Types.h, I wish the C++ 2003 standard had the numbered typedefs from C99 (int32_t, etc), sucks having to redefine it constantly. (The _t in the standard ones seems rather akward and redundant too)
You mention that it intended for use in realtime multithreaded applications, you might find that boost's shared_ptr is useful, or has useful techniques you might want to look at, it is now thread-safe and lock-free (on most CPUs), so you can get quite some performance gain if you are running some thread-heavy stuff.
Thanks for the comments, you seem to have some knowledge of lockless multithreaded programming, is it from audio/midi programming, RTOS programming, or something you've come across eg through boost? It seems to have become almost unknown since Motorola 68000 series days.
I guess you mean boost::shared_ptr is using compare and swap instructions via inline asm to make it threadsafe and lockless. I'll look into it, thanks. Threadsaftey is only an issue for one of my smart pointers- NewSmartPtr, the others rely on LDK::create<> and LDK::destroy<> instead of new and delete, and so cannot be shared between threads. The allocator uses thread-local storage to avoid locks entirely, it is an attempt to make heap allocation as cheap as stack allocation, however I have yet to look into locality of reference issues.
I'm avoiding things like boost, it in particular has grown too huge with too many interdependencies. No problem with pinching the odd idea though. A possible change to my smart pointers is deferred deletetion: when the reference count hits 0 the object gets placed in a queue to be deleted during idle time.
The philosophy of LDK threading is large partions of program communicating via lockless queues with clear separation between realtime and non realtime parts. It's a pattern I came across in high end audio software, it's possible with lots of tweaking to get around 1 millisecond latency between audio input, processing and output on linux with these and other techniques combined with SCHED_FIFO priority. Those sorts of latencies are useful for all sorts of things otherwise impossible without an RTOS, and it's particularly interesting in combination with embedded linux.
My lockess queue template requires memory barriers for smp architectures I've discovered. The design is threadsafe on uniprocessors without them. I'm planning on a more elaborate queue using compare and swap techniques, and have a whole bunch of research papers on lockless data structures. Another plan is to add ">>" and "<<" operators for a bunch of types to VFile, sort out the UTF8 problems, add cross platform plugin loading, also custom String (std::string is crap) and FastArray classes optimised for my allocator and a few other bits and pieces.
Right now I'm taking a break from things though, this stuff and a ton of unreleased code has become a "for fun" project and I'm feeling burnt out. Also I don't really care about maintaining MSVC compatability- it's been far more trouble than it's worth.
The hashtable names and : Partly I just don't like names with underscores, partly I wanted to keep my formatting consistant across LDK and more containers are planned, partly I don't think it matters much with a hashtable- certainly not for the use I had in mind- the symbol tables and hash tables of a scripting langauge. Feel free to hack it if you don't like it, though my preference would be adding short, standard names that call my methods. I've typedefed Hash::Iterator and Hash::ConstIterator to Hash::iterator and Hash::const_iterator for example.
I'm happy to provide sourceforge developer access for competent and ethical C++ programmers after having received and examined some patches. Please post questions via sourceforge however, as that's LDK's home and I've moved away from game related development and sumea.
I've updated the build and install instructions somewhat, and the API documentation (which is a work in progress nearing completion) is uploading right now to http://ldk.sourceforge.net (sourceforge gave me a subdomain last night)