4 ms·

klib? https://github.com/attractivechaos/klib https://github.com/attractivechaos/klib

by kleton 5y ago

glouwbug 5y ago
CTL. https://github.com/glouw/ctl https://github.com/glouw/ctl It's functionally blackbox compatible with the STL for the major containers. Unless you're writing heap spaced firmware where C++ with an STL isn't available I recommend you just use modern day C++. Unless, of course, you want blazing fast compile times!
- ludamad 5y ago
  I'm curious about how much easier it is to optimize compiler time for macros rather than templates here. In theory they wouldn't be all that different, but in practice it doesn't seem so
  - glouwbug 5y ago
    CTL just copy pastes a bunch of code via an include for each new type. The following two tidbits are basically the same thing: CTL #define P #define T int #include <vec.h> STL #include <vector> template class std::vector<int>; C++ with its STL is just dramatically slower at compiling it all. C loves to chew through its basic syntax and O(1) lookup since every symbol is essentially unique (take that C++ and your function overloading!)
- eps 5y ago
  Intrusive containers are a way more natural fit for a C codebase. They are also a superior choice for C++ code. The one and only plus of STL containers is that they come standard.
  - naasking 5y ago
    I can sort of see some arguments for this conclusion, but I've never read any comprehensive argument or guideline explaining why intrusive containers are a good idea, and how best to use them. Do you have something like this?
    - eps 5y ago
      Once you try both, it's really just some common sense: 1. Operating on intrusive containers requires no heap operations, all control structures are preallocated. This is golden, and in more ways than one. 2. Keeping an item in multiple containers has the exact same semantics as storing it in just one. With STL it requires switching from storing items to storing pointers to them. Meaning that you can't throw foo from an existing list into some extra map without reworking all list-related code.
      - naasking 5y ago
        > Operating on intrusive containers requires no heap operations, all control structures are preallocated. This is golden, and in more ways than one. I get the advantages in abstract, and intrusive containers are common in kernel programming where allocation is strictly controlled and objects have limited membership, I'm just curious about the applicability to more general programming and domain modelling, and whether it scales in terms of developer productivity. For instance, how common are programs that store objects in multiple dictionaries and/or multiple lists simultaneously? You say this has the same semantics as storing it one container, but I'm not clear what you mean by this. Also, if you want to extend an object's membership to another container, what sorts of changes are required compared to non-intrusive containers [1]? Adding an object to a non-intrusive container is a simple local change, ie. container.Add(item), but with an intrusive container you need to actually extend the type definition itself, an intrusive non-local change; this should inhibit some forms of extension, so I want a better understanding of that impact. Finally, do intrusive containers retain meaningful advantages in languages with garbage collection? Certainly less allocation is one obvious benefit, but are there downsides? Functional languages in particular emphasize composing small scale, orthogonal data types to build programs, which intrusive containers basically turns inside out. Intrusive containers almost seem like something a clever functional compiler should do for you, ie. it's a program transformation kind of like array of structs can be functionally transformed to a more efficient struct of arrays. A flow sensitive analysis identifies the collections to which an object might be added, and adds the requisite bookeeping info to the data type during compilation. Would be an interesting research topic at least. [1] For instance, in a kernel, a process could be waiting on multiple file descriptors, or timers, or any number of other things, all of which might have their own queues to which the process might be added.
- potiuper 5y ago
  Strange to focus on compile times given libraries can be precompiled to object files over not having to deal with Turing complete templates.
- naasking 5y ago
  Neat, I actually prototyped something like this a few years ago to see how closely I could reproduce parametric polymorphism in C using macros, and it ends up looking a lot like Ada generic packages. The only difference from your style is that I have a "clever" hack to support generic-functions as well and the error messages preserve those names, so your example from github would look something like this: #include <stdio.h> #define P #define T int #include <vec.h> int compare(int* a, int* b) { return *b < *a; } int main(void) { vec(int) a = vec_init(int)(); vec_push_back(int)(&a, 9); vec_push_back(int)(&a, 1); vec_push_back(int)(&a, 8); vec_push_back(int)(&a, 3); vec_push_back(int)(&a, 4); vec_sort(int)(&a, compare); foreach(vec(int), &a, it) printf("%d\n", *it.ref); vec_free(int)(&a); } I really should finish that writeup some day.

klib? https://github.com/attractivechaos/klib https://github.com/attractivechaos/klib

by kleton 5y ago

klib? https://github.com/attractivechaos/klib https://github.com/attractivechaos/klib

CTL. https://github.com/glouw/ctl https://github.com/glouw/ctl It's functionally blackbox compatible with the STL for the major containers. Unless you're writing heap spaced firmware where C++ with an STL isn't available I recommend you just use modern day C++. Unless, of course, you want blazing fast compile times!

ludamad 5y ago
I'm curious about how much easier it is to optimize compiler time for macros rather than templates here. In theory they wouldn't be all that different, but in practice it doesn't seem so
- glouwbug 5y ago
  CTL just copy pastes a bunch of code via an include for each new type. The following two tidbits are basically the same thing: CTL #define P #define T int #include <vec.h> STL #include <vector> template class std::vector<int>; C++ with its STL is just dramatically slower at compiling it all. C loves to chew through its basic syntax and O(1) lookup since every symbol is essentially unique (take that C++ and your function overloading!)
eps 5y ago
Intrusive containers are a way more natural fit for a C codebase. They are also a superior choice for C++ code. The one and only plus of STL containers is that they come standard.
- naasking 5y ago
  I can sort of see some arguments for this conclusion, but I've never read any comprehensive argument or guideline explaining why intrusive containers are a good idea, and how best to use them. Do you have something like this?
  - eps 5y ago
    Once you try both, it's really just some common sense: 1. Operating on intrusive containers requires no heap operations, all control structures are preallocated. This is golden, and in more ways than one. 2. Keeping an item in multiple containers has the exact same semantics as storing it in just one. With STL it requires switching from storing items to storing pointers to them. Meaning that you can't throw foo from an existing list into some extra map without reworking all list-related code.
    - naasking 5y ago
      > Operating on intrusive containers requires no heap operations, all control structures are preallocated. This is golden, and in more ways than one. I get the advantages in abstract, and intrusive containers are common in kernel programming where allocation is strictly controlled and objects have limited membership, I'm just curious about the applicability to more general programming and domain modelling, and whether it scales in terms of developer productivity. For instance, how common are programs that store objects in multiple dictionaries and/or multiple lists simultaneously? You say this has the same semantics as storing it one container, but I'm not clear what you mean by this. Also, if you want to extend an object's membership to another container, what sorts of changes are required compared to non-intrusive containers [1]? Adding an object to a non-intrusive container is a simple local change, ie. container.Add(item), but with an intrusive container you need to actually extend the type definition itself, an intrusive non-local change; this should inhibit some forms of extension, so I want a better understanding of that impact. Finally, do intrusive containers retain meaningful advantages in languages with garbage collection? Certainly less allocation is one obvious benefit, but are there downsides? Functional languages in particular emphasize composing small scale, orthogonal data types to build programs, which intrusive containers basically turns inside out. Intrusive containers almost seem like something a clever functional compiler should do for you, ie. it's a program transformation kind of like array of structs can be functionally transformed to a more efficient struct of arrays. A flow sensitive analysis identifies the collections to which an object might be added, and adds the requisite bookeeping info to the data type during compilation. Would be an interesting research topic at least. [1] For instance, in a kernel, a process could be waiting on multiple file descriptors, or timers, or any number of other things, all of which might have their own queues to which the process might be added.
potiuper 5y ago
Strange to focus on compile times given libraries can be precompiled to object files over not having to deal with Turing complete templates.
naasking 5y ago
Neat, I actually prototyped something like this a few years ago to see how closely I could reproduce parametric polymorphism in C using macros, and it ends up looking a lot like Ada generic packages. The only difference from your style is that I have a "clever" hack to support generic-functions as well and the error messages preserve those names, so your example from github would look something like this: #include <stdio.h> #define P #define T int #include <vec.h> int compare(int* a, int* b) { return *b < *a; } int main(void) { vec(int) a = vec_init(int)(); vec_push_back(int)(&a, 9); vec_push_back(int)(&a, 1); vec_push_back(int)(&a, 8); vec_push_back(int)(&a, 3); vec_push_back(int)(&a, 4); vec_sort(int)(&a, compare); foreach(vec(int), &a, it) printf("%d\n", *it.ref); vec_free(int)(&a); } I really should finish that writeup some day.