Quicker Sorting
AC’s sort algorithm is significantly faster than the standard qsort and C++’s implementation.
This is accomplished through improved detection for sorted, equal, and reversed records at little to no computational cost, and hand-unrolling heap sorts for small arrays.
ac_sort vs std::sort
Ordered test (time in microseconds)
items ac_sort std::sort % gain
100 0.043 0.341 693.023%
10,000 3.228 29.921 826.921%
1,000,000 393.470 3,315.230 742.562%
Equal test (time in microseconds)
items ac_sort std::sort % gain
100 0.045 0.304 575.556%
10,000 3.154 25.942 722.511%
1,000,000 384.580 3,202.080 732.617%
Reverse test (time in microseconds)
items ac_sort std::sort % gain
100 0.084 0.536 538.095%
10,000 6.197 56.242 807.568%
1,000,000 963.120 5,984.830 521.400%
Random test (time in microseconds)
items ac_sort std::sort % gain
100 0.388 1.576 306.186%
10,000 411.915 506.590 22.984%
1,000,000 60,816.670 77,113.870 26.797%
ac_sort vs qsort
Ordered test (time in microseconds)
items ac_sort qsort % gain
100 0.043 0.486 1030.233%
10,000 3.228 40.842 1165.242%
1,000,000 393.470 4,379.690 1013.094%
Equal test (time in microseconds)
items ac_sort qsort % gain
100 0.045 0.294 553.333%
10,000 3.154 28.190 793.786%
1,000,000 384.580 2,784.150 623.946%
Reverse test (time in microseconds)
items ac_sort qsort % gain
100 0.084 2.212 2533.333%
10,000 6.197 216.290 3390.237%
1,000,000 963.120 22,208.090 2205.849%
Random test (time in microseconds)
items ac_sort qsort % gain
100 0.388 1.952 403.093%
10,000 411.915 777.368 88.720%
1,000,000 60,816.670 111,768.980 83.780%
Parse Speed (MB/sec) ac_json rapidjson % gain
canada.json 1222 374 226.738%
citm_catalog.json 1145 943 21.421%
twitter.json 1000 543 84.162%
overall 1158 511 126.614%
Dump Speed (MB/sec) ac_json rapidjson % gain
canada.json 1192 187 537.433%
citm_catalog.json 591 338 74.852%
twitter.json 1094 462 136.797%
overall 1158 511 126.614%
Reduce Memory Errors
AC’s allocator aids in development as memory leaks, double frees, and incorrect frees are reported.
The allocation aids can be compiled out for production. Often programs will run at 90-99% of the optimized speed with the allocation aids enabled.
#include <stdio.h>
int main(int argc, char *argv[]) {
printf("Demo to show how allocations are tracked\n");
char *s = ac_strdup(argv[0]);
// ac_free(s);
return 0;
}
$ ./detecting_memory_loss
Demo to show how allocations are tracked
24 byte(s) allocated in 1 allocations (40 byte(s) overhead)
detecting_memory_loss.c:7: 24
#include "ac_pool.h"
#include <stdio.h>
int main(int argc, char *argv[]) {
ac_pool_t *pool = ac_pool_init(65536);
char *cmd = ac_pool_strdupf(pool, "CMD: %s", argv[0]);
printf("%s\n", cmd);
ac_buffer_t *bh = ac_buffer_pool_init(pool, 256);
ac_buffer_setf(bh, "The buffer will be destroyed when pool is destroyed!");
printf("%s\n", ac_buffer_data(bh));
ac_pool_destroy(pool);
return 0;
}
$ ./pool_demo
CMD: ./pool_demo
The buffer will be destroyed when pool is destroyed!
Goals of this Project:
- To provide an open source collection of algorithms necessary to build complex applications
- To help engineers understand algorithms and C better, so that they can create their own
- To help people to learn what it takes to create something new
- Build scalable applications using technology like Kubernetes, nginx, and docker
About this Project:
Another C Library rebuilds, and in some cases, improves upon, some of the most useful Computer Science algorithms from the ground up. The library is Open Source and was created in late 2019, so it is currently still under very active development.
Andy and Daniel Curtis created this library to serve as a starting point for C developers. Whether you're diving into C for the first time or building complex applications, Another C Library offers tools for both learning and building.