4 ms·

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

by 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.

by 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.