DAS - dynamically allocated storage

A simple dynamic allocation library with a stack and double ended queue implementation.

Features

• array-like stack (DasStk)
• double ended queue (DasDeque)
• thread local custom allocator (DasAlctor)
• allocation API that uses the custom allocator (das_alloc, das_realloc, das_dealloc)
• compiles as C11 and C++11
• simple API to keep user code as simple as possible.
  • no type decorations required on the Stack and Deque API
  • out of memory errors are never returned, instead they are handled through a global thread local callback
• no executable bloat
  • we define a single function for each operation, that can be used for all types of DasStk/DasDeque
• fast compile times
  • we do not generate any code, other than single line macros

Supported Platforms

The code should ideally compile on any C and C++ compiler with thread_local and typeof (language extension) support.
C11 and C++11 are the current targets, since this is when thread_local was included in the standards.
If it doesn't mess with the code too much, I am open to supporting older versions if anyone wants to submit some patches :)

• Windows (clang)
• Linux (clang & gcc)
• MacOS (clang) - untested but should work since it's clang. let me know if you can test it!
• IOS (clang) - untested but should work since it's clang. let me know if you can test it!
• Android (gcc) - untested but should work since it's gcc. let me know if you can test it!

How to Build

You only need to copy das.h and das.c into your project.

In one of your C or C++ compilation units, include the das.h header and das.c source files like so:

#include "das.h"
#include "das.c"

To use the library in other files, you need to include the das.h header.

#include "das.h"

Documentation

Most structs, functions and macros have their documentation above them in the das.h header file.

If you are looking for examples, look in the das_examples.c file. There are comments to guide you through and it is suggested that you follow linearally to learn the API.
In that file we have:

• stk_example()
  • initializing a stack
  • pushing and popping elements
  • inserting and removing elements
• deque_example()
  • initializing a double ended queue
  • pushing and popping elements from both ends
• alloc_example()
  • allocation API
• out_of_mem_handler_example()
  • out of memory handler
• custom_allocator_example()
  • using a custom allocator (linear allocator)

Project Structure

• das.c - main source file
• das.h - main header file
• das_examples.c - examples with comments, it is suggested that you follow linearally to learn the API.
• das_test.c - test file for C
• cpp_das_test.cpp - test file for C++
• run_test.sh - posix shell script for compiling and running the two test files
  • compiles using gcc and clang
• run_test.bat - batch script for compiling and running the two test files
  • compiles using clang
• benchmark - a directory that holds a benchmark for compiling DasStk vs std::vector. See below for more info.

Benchmarks

This benchmark tests compiling different DasStk implementations vs std::vector. In all tests except cpp_vector_trio_main, we are handling 130 different structures. For each of these, in the main function, a DasStk/std::vector is created and then elements get pushed on to it. These results are on an Intel i5 8250u CPU using Clang 10 on Linux in July 2020. No optimization level has been specified. The results are ordered by time where the fastest test comes first.

• das_main.c
  • using DasStk
  • time: 0.174s
  • size: 51K
  • main_function_size: 28K
• cpp_das_main.cpp
  • using DasStk compiled as C++
  • time: 0.236s
  • size: 51K
  • main_function_size: 28K
• cpp_vector_trio_main.cpp
  • using std::vector with 3 different structures instead of 130.
  • so the size will be less because of the small main function.
  • time: 0.289s
  • size: 40K
  • main_function_size: 730B
• cpp_vector_main.cpp
  • using std::vector
  • time: 3.430s
  • size: 1.1M
  • main_function_size: 30K

We do not have any run-time benchmarks, since these are unlikely to reflect what happens in the real world. At the end of the day, different implementations of stacks and deques are very similar.

However std::vector will generate a optimized function for every implementation. But realistically, where DAS passes in size and align arguments, std::vector have constants precompiled in. As far as I know, thats a very negligible win if any at all. When pushing an popping a single element, std::vector could have optimized load and store instructions for intrinsic data types. Instead of how DAS uses a memcpy for all data types. These are the only two benefits that I could think of. Personally I don't think it's worth the time to compile these different versions just for these things.

In DAS, for each operation we have a single function that is used for every type. So there is a single push function for DasStk that is used for all types. These functions are not complicated and will fit in the instruction cache better. So if you are handling many different types of stacks or deques, then DAS is probably better. But again as far as I know, this is probably very negligible if you are not doing huge amounts of data.

I hope this helps, do your own tests if you need :)