www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - D and a bazillion of small objects

reply "Yao G." <nospamyao gmail.com> writes:
Hello everybody.

What's the best practice or more efficient way to deal, in D, with lots of  
small objects? My problem is this: I have a small control, ListView. This  
control can have hundreds (and theoretically thousands) of items  
(ListViewItem instances, to be precise). And, in turn each one of this  
ListViewItems can own sub-items (ListViewSubItem instances), effectively  
creating an humongous quantity of small objects.

Should I just go and create all of those items as classes? I have the  
feeling that this not very efficient (a lot of small heap allocations).  
There's also the possibility of make them structs. But then I would have  
the issue of passing value objects in methods and losing whatever change I  
made (because I would be modifying a copy of the original). To solve this  
I could make an internal, Impl structure, and then use reference counting  
to manage the copies and to make effective all the item modification  
across all copies. But then I would be where I started: doing tons of heap  
allocations.

So, how should I deal with this issue?

Thanks.

Yao G.
Jun 02 2010
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Yao G.:


 Hello everybody.
 
 What's the best practice or more efficient way to deal, in D, with lots of  
 small objects? My problem is this: I have a small control, ListView. This  
 control can have hundreds (and theoretically thousands) of items  
 (ListViewItem instances, to be precise). And, in turn each one of this  
 ListViewItems can own sub-items (ListViewSubItem instances), effectively  
 creating an humongous quantity of small objects.
 
 Should I just go and create all of those items as classes? I have the  
 feeling that this not very efficient (a lot of small heap allocations).  
 There's also the possibility of make them structs. But then I would have  
 the issue of passing value objects in methods and losing whatever change I  
 made (because I would be modifying a copy of the original). To solve this  
 I could make an internal, Impl structure, and then use reference counting  
 to manage the copies and to make effective all the item modification  
 across all copies. But then I would be where I started: doing tons of heap  
 allocations.
 
 So, how should I deal with this issue?


First of all run your program and profile it. If it's fast enough for your
purposes, or if the slow parts are elsewhere then you can avoid to optimize the
allocation of all those objects.

Otherwise, or if you are writing library code it has to be fast regardless. If
you can change those objects into structs, then it's "easy", you can pass them
in functions by ref, keeping their changes, and you can allocate them in large
chunks, using some kind of arena, pool or stack with a freelist, etc. In my
dlibs1 I have something like this to allocate chunks of structs in a pool.

If you must use objects, then you can create the same pools, using placement
new. Unfortunately placement new is now deprecated in D2 :-) (If you are using
D1 it's OK). Andrei has recently shown a TightArray to replace placement new in
D2, but I think it's not good enough yet to solve your problem (but I probably
Andrei will improve it).

Bye,
bearophile
Jun 02 2010
parent reply "Yao G." <nospamyao gmail.com> writes:
Thanks bearophile.

With respect to passing structs as reference, I also have this problem. In  
the widget, I have a opIndex method, that returns a ListViewItem given an  
index (like an array). When opIndex return the instance I'm looking for,  
and then I modify some property (a image index, for example) the change is  
only visible in the returned copy, but the internal instance, the one  
stored in the collection (array in this case) is not modified.

Now, about the speed. Currently, I'm not so concerned about speed. First I  
want to make this work correctly, and then profile to improve execution  
speed, etc. What worries me is the hypothetical case of a heap thrashed or  
severely fragmented because the several small allocations. Something that  
I don't mentioned in the previous message, is that in each item instance  
there's a string with the text to display. So not only I need to allocate  
for each item instance, but also allocate the text string for each one  :D

I think the idea of a memory pool or freelist is good. Can you point me  
where can I see your libs?

Thanks again.

Yao G.


On Wed, 02 Jun 2010 19:18:37 -0500, bearophile <bearophileHUGS lycos.com>  
wrote:


 Yao G.:


 Hello everybody.

 What's the best practice or more efficient way to deal, in D, with lots  
 of
 small objects? My problem is this: I have a small control, ListView.  
 This
 control can have hundreds (and theoretically thousands) of items
 (ListViewItem instances, to be precise). And, in turn each one of this
 ListViewItems can own sub-items (ListViewSubItem instances), effectively
 creating an humongous quantity of small objects.

 Should I just go and create all of those items as classes? I have the
 feeling that this not very efficient (a lot of small heap allocations).
 There's also the possibility of make them structs. But then I would have
 the issue of passing value objects in methods and losing whatever  
 change I
 made (because I would be modifying a copy of the original). To solve  
 this
 I could make an internal, Impl structure, and then use reference  
 counting
 to manage the copies and to make effective all the item modification
 across all copies. But then I would be where I started: doing tons of  
 heap
 allocations.

 So, how should I deal with this issue?


 First of all run your program and profile it. If it's fast enough for  
 your purposes, or if the slow parts are elsewhere then you can avoid to  
 optimize the allocation of all those objects.

 Otherwise, or if you are writing library code it has to be fast  
 regardless. If you can change those objects into structs, then it's  
 "easy", you can pass them in functions by ref, keeping their changes,  
 and you can allocate them in large chunks, using some kind of arena,  
 pool or stack with a freelist, etc. In my dlibs1 I have something like  
 this to allocate chunks of structs in a pool.

 If you must use objects, then you can create the same pools, using  
 placement new. Unfortunately placement new is now deprecated in D2 :-)  
 (If you are using D1 it's OK). Andrei has recently shown a TightArray to  
 replace placement new in D2, but I think it's not good enough yet to  
 solve your problem (but I probably Andrei will improve it).

 Bye,
 bearophile



-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
Jun 02 2010
next sibling parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Yao G. <nospamyao gmail.com> wrote:


 Thanks bearophile.

 With respect to passing structs as reference, I also have this problem.  
 In the widget, I have a opIndex method, that returns a ListViewItem  
 given an index (like an array). When opIndex return the instance I'm  
 looking for, and then I modify some property (a image index, for  
 example) the change is only visible in the returned copy, but the  
 internal instance, the one stored in the collection (array in this case)  
 is not modified.


So use a ref return.

ref T opIndex( int index ) {
   return arr[index];
}

-- 
Simen
Jun 02 2010
parent "Yao G." <nospamyao gmail.com> writes:
Yeah. I think I'll do that. I just hope that no temporary copy is created  
in other item access or manipulation.

Thanks.

On Wed, 02 Jun 2010 20:04:53 -0500, Simen kjaeraas  
<simen.kjaras gmail.com> wrote:


 Yao G. <nospamyao gmail.com> wrote:


 Thanks bearophile.

 With respect to passing structs as reference, I also have this problem.  
 In the widget, I have a opIndex method, that returns a ListViewItem  
 given an index (like an array). When opIndex return the instance I'm  
 looking for, and then I modify some property (a image index, for  
 example) the change is only visible in the returned copy, but the  
 internal instance, the one stored in the collection (array in this  
 case) is not modified.


 So use a ref return.

 ref T opIndex( int index ) {
    return arr[index];
 }



-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
Jun 02 2010
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Yao G.:

 I think the idea of a memory pool or freelist is good. Can you point me  
 where can I see your libs?


Instead of just giving you a link to the dlibs1, I've extracted the relevant
code and adapted it to D2:
http://codepad.org/Ug5Z5qum

I have tested it enough with D1 but only a bit with D2, so be careful. This
code can be improved in numerous ways :-) Something similar can be useful in
Phobos2 too, I think Tango has something similar (but probably better).

Bye,
bearophile
Jun 03 2010
parent "Yao G." <nospamyao gmail.com> writes:
Thanks bearophile. I'll give it a try later.

--
Yao.G

On Thu, 03 Jun 2010 12:27:20 -0500, bearophile <bearophileHUGS lycos.com>  
wrote:


 Yao G.:

 I think the idea of a memory pool or freelist is good. Can you point me
 where can I see your libs?


 Instead of just giving you a link to the dlibs1, I've extracted the  
 relevant code and adapted it to D2:
 http://codepad.org/Ug5Z5qum

 I have tested it enough with D1 but only a bit with D2, so be careful.  
 This code can be improved in numerous ways :-) Something similar can be  
 useful in Phobos2 too, I think Tango has something similar (but probably  
 better).

 Bye,
 bearophile
Jun 03 2010
prev sibling parent Kagamin <spam here.lot> writes:
You can use another design: feed your control with your items collection and
interface like

string opIndex(size_t item, size_t subItem);
string opIndexAssign(size_t item, size_t subItem, string newValue);
void sort(size_t subItem, bool asc=true);

which will be used by the control to present the items. Then implement and fill
your collection as you want.
Jun 03 2010