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