View mode: basic / threaded / horizontal-split · Log in · Help
September 01, 2012
Embedded non-assignable containers
Hey,

I recently read an interesting blog Why should I have written ZeroMQ in C,
not C++ (part II) <http://www.250bpm.com/blog:8> by Martin Sústrik. The
title is misleading; to me its main observation is that object oriented
program may not lead to the most performant implementation. After reading
the blog I asked myself I would I implement this in D? I thought we could
use mixin and template mixin to implement this in a more
manageable/scalable way. The complete source code is at Embedded
Container<http://dpaste.dzfl.pl/14ddac09>
.

To make a type "double linkable" the developer needs to mixin the following
mixin template:

mixin template DoubleLinkable()
> {
>   typeof(this) next;
>   typeof(this) prev;
> }


The next and prev pointer can be access with the help of mixin by using the
following templates:

T* next(T, string name)(T node) pure nothrow const

{

 mixin("return &(node." ~ name ~ ".next);");

}



T* prev(T, string name)(T node) pure nothrow const

{

 mixin("return &(node." ~ name ~ ".prev);");

}


To use the above abstraction the developer just needs to do the following:

class Person
> {
>   int age;
>   int weight;
>   mixin DoubleLinkable people;
> }



void main()

{

 auto list = new DoubleLinkedList!(Person, "people")();


>   auto person1 = new Person(6, 60);

 list.pushFront(person1);


>   auto person2 = new Person(25, 160);

 list.pushFront(person2);


>   auto person3 = new Person(11, 100);

 list.pushFront(person3);


>   list.erase(person2);

 list.erase(person3);

 list.erase(person1);

}



I am not a big fan of the template signature 'class DoubleLinkedList(T,
string name)' but I couldn't figure out a better way of allowing one object
to be embedded in multiple containers. Thoughts? Any idea how this can be
improved so that it is easier to use and read?

Thanks,
-Jose
September 02, 2012
Re: Embedded non-assignable containers
José Armando García Sancio:

> I recently read an interesting blog Why should I have written 
> ZeroMQ in C,
> not C++ (part II) <http://www.250bpm.com/blog:8> by Martin 
> Sústrik. The
> title is misleading; to me its main observation is that object 
> oriented
> program may not lead to the most performant implementation.

Isn't he talking about Boost intrusive lists?

http://www.boost.org/doc/libs/1_51_0/doc/html/intrusive/intrusive_vs_nontrusive.html

One advantage of the NOT intrusive stl list is that if you have 
to transverse the linked list very often, the L1 cache only sees 
the smal(ler) "helpers" (see this image: 
http://250bpm.wdfiles.com/local--files/blog:8/cpp1.png ) this 
probably leads to faster traversal times.

On the other hand linked lists are kind of dead, today their need 
is uncommon.

Bye,
bearophile
September 04, 2012
Re: Embedded non-assignable containers
On Sat, Sep 1, 2012 at 6:40 PM, bearophile <bearophileHUGS@lycos.com> wrote:

> José Armando García Sancio:
>
>  I recently read an interesting blog Why should I have written ZeroMQ in C,
>> not C++ (part II) <http://www.250bpm.com/blog:8> by Martin Sústrik. The
>>
>> title is misleading; to me its main observation is that object oriented
>> program may not lead to the most performant implementation.
>>
>
> Isn't he talking about Boost intrusive lists?
>
> http://www.boost.org/doc/libs/**1_51_0/doc/html/intrusive/**
> intrusive_vs_nontrusive.html<http://www.boost.org/doc/libs/1_51_0/doc/html/intrusive/intrusive_vs_nontrusive.html>
>
> Basically.


> One advantage of the NOT intrusive stl list is that if you have to
> transverse the linked list very often, the L1 cache only sees the smal(ler)
> "helpers" (see this image: http://250bpm.wdfiles.com/**
> local--files/blog:8/cpp1.png<http://250bpm.wdfiles.com/local--files/blog:8/cpp1.png>) this probably leads to faster traversal times.
>

Maybe. But I suspect that you are traversing the list to at least read into
the object so I think this become a wash if not worst.


>

On the other hand linked lists are kind of dead, today their need is
> uncommon.
>

How so? Immutable single linked list are nice for multi-threaded
programming. They are heavily used by functional languages like Haskell,
Scala, Clojure, etc.

Bye,
> bearophile
>
Top | Discussion index | About this forum | D home