www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.dtl - mintl.Set help please

reply Ivan Senji <ivan.senji_REMOVE_ _THIS__gmail.com> writes:
I decided to replace my own stupid set in some projects with
mintl's set but i ran into some problems:

class A
{
   this(int x, int[] y)
   {
     x_ = x;
     y_ = y;
   }
   int x_;
   int[] y_;
}

Set!(A) a;

a.add(new A(3,array!(int)(1,2,3)));

And i get:

try_mintl.obj(try_mintl)
  Error 42: Symbol Undefined __init_22TypeInfo_C9try_mintl1A

I never had to deal with TypeInfo's before, so i don't know what
to do? Do i have to create a TypeInfo class for A?

What operators does mintl.Set need to work? opEquals? opCmp? toHash?

Thanks!
Sep 18 2005
next sibling parent reply Ivan Senji <ivan.senji_REMOVE_ _THIS__gmail.com> writes:
Ivan Senji wrote:

...
 Set!(A) a;
 
 a.add(new A(3,array!(int)(1,2,3)));
 
 And i get:
 
 try_mintl.obj(try_mintl)
  Error 42: Symbol Undefined __init_22TypeInfo_C9try_mintl1A
 

I now added TypeInfo ti=typeid(A); before Set!(A) a; and now it links but i get: Error: illegal add argument when trying to add new A to set? Very strange!
Sep 18 2005
parent reply Ivan Senji <ivan.senji_REMOVE_ _THIS__gmail.com> writes:
Ivan Senji wrote:
 Ivan Senji wrote:

 and now it links but i get:
 Error: illegal add argument

There was a mistake elsewhere in code. But now i have another problem: int main() { TypeInfo ti=typeid(A); Set!(A) a; a.add(new A(3,array!(int)(1,2,3))); assert( a.length == 1); a.add(new A(3,array!(int)(1,2,3))); assert( a.length == 1); return 0; } the last assert fails but i don't wan't it to fail. I guess there is something wrong on my opCmp and opEquals but i don't see what? A looks like this: class A { this(int x, int[] y) { x_ = x; y_ = y; } int opCmp(Object o) { A a = cast(A)o; if(this.x_ != a.x_){return this.x_ - a.x_;} if(this.y_.length != a.y_.length) {return this.y_.length - a.y_.length;} for(int i=0; i<this.y_.length; i++) { if(this.y_[i] != a.y_[i]){return this.y_[i] - a.y_[i];} } return 0; } int opEquals(Object o) { A a = cast(A)o; if(this.x_ != a.x_){return false;} if(this.y_.length != a.y_.length){return false;} for(int i=0; i<this.y_.length; i++) { if(this.y_[i] != a.y_[i]){return false;} } return true; } private { int x_; int[] y_; } } How should i write these operators? Thanks again! :)
Sep 18 2005
parent reply "Ben Hinkle" <ben.hinkle gmail.com> writes:
"Ivan Senji" <ivan.senji_REMOVE_ _THIS__gmail.com> wrote in message 
news:dgjq3j$2hlp$1 digitaldaemon.com...
 Ivan Senji wrote:
 Ivan Senji wrote:

 and now it links but i get:
 Error: illegal add argument

There was a mistake elsewhere in code. But now i have another problem: int main() { TypeInfo ti=typeid(A); Set!(A) a; a.add(new A(3,array!(int)(1,2,3))); assert( a.length == 1); a.add(new A(3,array!(int)(1,2,3))); assert( a.length == 1); return 0; } the last assert fails but i don't wan't it to fail.

By default Set is implemented as a hashtable so you need to override toHash to compute the same hash value for both objects. The default Object.toHash generates distinct hashes for each instance. If you don't want to use a hashtable you can tell Set to use a different backing container like SortedSet which doesn't need a hash function - all it needs is opCmp and opEquals (or maybe just opCmp - I can't even remember off the top of my head).
Sep 18 2005
parent reply Ivan Senji <ivan.senji_REMOVE_ _THIS__gmail.com> writes:
Ben Hinkle wrote:
 "Ivan Senji" <ivan.senji_REMOVE_ _THIS__gmail.com> wrote in message 
 news:dgjq3j$2hlp$1 digitaldaemon.com...
 
Ivan Senji wrote:

Ivan Senji wrote:

and now it links but i get:
Error: illegal add argument

There was a mistake elsewhere in code. But now i have another problem: int main() { TypeInfo ti=typeid(A); Set!(A) a; a.add(new A(3,array!(int)(1,2,3))); assert( a.length == 1); a.add(new A(3,array!(int)(1,2,3))); assert( a.length == 1); return 0; } the last assert fails but i don't wan't it to fail.

By default Set is implemented as a hashtable so you need to override toHash to compute the same hash value for both objects. The default Object.toHash generates distinct hashes for each instance.

Thanks. I figured it out after i posted the question.
 If you don't want to use a hashtable you can tell Set to use a different 
 backing container like SortedSet which doesn't need a hash function - all it 
 needs is opCmp and opEquals (or maybe just opCmp - I can't even remember off 
 the top of my head). 
 

Just replaced Set!(A) with SortedSet!(A) and it works! Just one more question and i promise to stop. Which one is better hashtable or SortedAA if i have a lot of lookups to see if an object is stored in there. To be honest i didn't like the way mintl uses structs for containers when i looked at it some time ago but i am changing my mind because it looks really nice. :-) Suggestion: did you think about adding another add method to containers or replacing the current one : add(Value[] array...)? It could be used in more ways: container.add(1); container.add(1,2,3); int[] numbers = [1,2,3,4,5]; container.add(numbers); And once again: thanks for all the help and mintl.
Sep 18 2005
parent "Ben Hinkle" <ben.hinkle gmail.com> writes:
 If you don't want to use a hashtable you can tell Set to use a different 
 backing container like SortedSet which doesn't need a hash function - all 
 it needs is opCmp and opEquals (or maybe just opCmp - I can't even 
 remember off the top of my head).

Just replaced Set!(A) with SortedSet!(A) and it works! Just one more question and i promise to stop.

no problem - I'm glad to hear someone trying it out.
 Which one is better hashtable or SortedAA if i have a lot of lookups
 to see if an object is stored in there.

Probably hashtable.
 To be honest i didn't like the way mintl uses structs for containers
 when i looked at it some time ago but i am changing my mind because
 it looks really nice. :-)

cool! Thanks for giving it another chance.
 Suggestion: did you think about adding another add method to containers or 
 replacing the current one : add(Value[] array...)? It could be used in 
 more ways:
 container.add(1);
 container.add(1,2,3);
 int[] numbers = [1,2,3,4,5];
 container.add(numbers);

good idea.
 And once again: thanks for all the help and mintl.

Sep 18 2005
prev sibling next sibling parent "Ben Hinkle" <ben.hinkle gmail.com> writes:
"Ivan Senji" <ivan.senji_REMOVE_ _THIS__gmail.com> wrote in message 
news:dgjkeq$2ci8$1 digitaldaemon.com...
I decided to replace my own stupid set in some projects with
 mintl's set but i ran into some problems:

 class A
 {
   this(int x, int[] y)
   {
     x_ = x;
     y_ = y;
   }
   int x_;
   int[] y_;
 }

 Set!(A) a;

 a.add(new A(3,array!(int)(1,2,3)));

 And i get:

 try_mintl.obj(try_mintl)
  Error 42: Symbol Undefined __init_22TypeInfo_C9try_mintl1A

 I never had to deal with TypeInfo's before, so i don't know what
 to do? Do i have to create a TypeInfo class for A?

 What operators does mintl.Set need to work? opEquals? opCmp? toHash?

 Thanks!

wierd. It looks like dmd needs more help in figuring out when to define the typeinfos. It works if I also supply set.d on the command line used when compiling the above code. I couldn't find any other way to tell the compiler it had to generate the symbol.
Sep 18 2005
prev sibling parent reply Ivan Senji <ivan.senji_REMOVE_ _THIS__gmail.com> writes:
I have replaced my Set class with the one in mintl and
i am having some problems. The entire program runs for 171 seconds
when i use my set, and 472s/553s when i use mintl's Set/SortedSet.

I expected mintl implementation to be a lot faster because mine uses
dynamic array for storing data.

Could the problem be that i link with mintl_debug.lib?
When i try to link with mintl.lib i get these errors:

lr.obj(lr)
  Error 42: Symbol Undefined _assert_5mintl3set
lr.obj(lr)
  Error 42: Symbol Undefined _assert_5mintl8sortedaa
lr.obj(lr)
  Error 42: Symbol Undefined _array_5mintl8sortedaa
--- errorlevel 3

I use Set!(int), add elements with addItem, but i also often
need to add to one set all the elements from another, and i
am doing it by iterating set.values() and inserting each one
with addItem.

Am I doing something wrong Ben?

PS
I now changed it not to iterate using Set.values but using
Set's opApply and i get 378 seconds, and i am still not happy.
Sep 20 2005
parent reply "Ben Hinkle" <ben.hinkle gmail.com> writes:
"Ivan Senji" <ivan.senji_REMOVE_ _THIS__gmail.com> wrote in message 
news:dgpunh$1u74$1 digitaldaemon.com...
I have replaced my Set class with the one in mintl and
 i am having some problems. The entire program runs for 171 seconds
 when i use my set, and 472s/553s when i use mintl's Set/SortedSet.

 I expected mintl implementation to be a lot faster because mine uses
 dynamic array for storing data.

 Could the problem be that i link with mintl_debug.lib?
 When i try to link with mintl.lib i get these errors:

 lr.obj(lr)
  Error 42: Symbol Undefined _assert_5mintl3set
 lr.obj(lr)
  Error 42: Symbol Undefined _assert_5mintl8sortedaa
 lr.obj(lr)
  Error 42: Symbol Undefined _array_5mintl8sortedaa
 --- errorlevel 3

 I use Set!(int), add elements with addItem, but i also often
 need to add to one set all the elements from another, and i
 am doing it by iterating set.values() and inserting each one
 with addItem.

 Am I doing something wrong Ben?

 PS
 I now changed it not to iterate using Set.values but using
 Set's opApply and i get 378 seconds, and i am still not happy.

Try running with profiling turned on (the -profile compiler flag). You probably won't have to rebuild mintl but who knows - I haven't tried it. With the undefined symbols the mintl.lib is built with compiler options -release -O and the mintl_debug.lib is built with -g (or something like that) so which one to use depends on how you compile your code. If you compile with -release then you want to link with mintl.lib. Otherwise link with mintl_debug.lib.
Sep 20 2005
parent reply Ivan Senji <ivan.senji_REMOVE_ _THIS__gmail.com> writes:
Ben Hinkle wrote:
 Try running with profiling turned on (the -profile compiler flag). You 
 probably won't have to rebuild mintl but who knows - I haven't tried it.
 With the undefined symbols the mintl.lib is built with compiler 
 options -release -O and the mintl_debug.lib is built with -g (or something 
 like that) so which one to use depends on how you compile your code. If you 
 compile with -release then you want to link with mintl.lib. Otherwise link 
 with mintl_debug.lib. 
 

Thanks for reply. The profiler output is very confusing. Example for one of my methods: My version: 1 21688 1475 1475 _D2lr7Grammar19calculateBEGINSWITHFZv Mintl(Set): 1 107029 1404 1404 _D2lr7Grammar19calculateBEGINSWITHFZv Mintl(SortedSet): 1 58309 1524 1524 _D2lr7Grammar19calculateBEGINSWITHFZv So i guess that my part of code in this function is doing the same thing but the total function takes 2-5 times longer, it uses a lot of Set!(int) adding elements, cheching for elements and iterating. When using mintl version (SortedSet) among the first 15 longes methods are these: 231237 21646605 10489211 45 _D5mintl8sortedaa11SortedAA_ik8SortedAA15opApplyIterStepFDFKS5mintl8sortedaa11SortedAA_ik8SortedAAZiiZi 1112802 7143301 2940878 2 _D5mintl8sortedaa11SortedAA_ik8SortedAA7getNodeFiiZPS5mintl8sortedaa11SortedAA_ik8SortedAA4Node 1112802 2224743 2070060 1 _D5mintl8sortedaa11SortedAA_ik8SortedAA11fixupSharedFZv 1089386 11071788 2039195 1 _D5mintl3set43Set_iS5mintl8sortedaa11SortedAA_ik8SortedAA3Set7addItemFiZv 1089386 9032592 1987612 1 _D5mintl8sortedaa11SortedAA_ik8SortedAA13opIndexAssignFkiZv 356673 1977680 1299222 3 _D5mintl8sortedaa11SortedAA_ik8SortedAA10insertNodeFikPS5mintl8sortedaa11SortedAA_ik8SortedAA4NodeiZPS5mintl8sortedaa11SortedAA_ik8SortedAA4Node 356673 536008 520647 1 _D5mintl8sortedaa11SortedAA_ik8SortedAA11insertFixupFPS5mintl8sortedaa11SortedAA_ik8SortedAA4NodeZv And these (when using Set): 142939 12051752 5905363 41 _D5mintl6hashaa9HashAA_ik6HashAA15opApplyIterStepFDFKS5mintl6hashaa9HashAA_ik6HashAAZiiZi 1089386 6197012 2152279 1 _D5mintl3set5Set_i3Set7addItemFiZv 1089386 4044732 2075248 1 _D5mintl6hashaa9HashAA_ik6HashAA13opIndexAssignFkiZv 1112802 1970573 1427748 1 _D5mintl6hashaa9HashAA_ik6HashAA7getNodeFiiZPPS5mintl6hashaa9HashAA_ik6HashAA4Node 57393 327416 306849 5 _D5mintl6hashaa9HashAA_ik6HashAA13initDataArrayFZv 142939 12616063 283985 1 _D5mintl6hashaa9HashAA_ik6HashAA44MOpApplyImpl_S5mintl6hashaa9HashAA_ik6HashAA14opApplyWithKeyFDFKiKkZiZi 142939 12332077 280324 1 _D5mintl6hashaa9HashAA_ik6HashAA18opApplyWithKeyStepFDFKiKkZiiZi Also on the top of mintl profiler output (in the part after ======== Timer Is 3579545 Ticks/Sec, Times are in Microsecs ========) there are these two methods: 231237 21646605 10489211 45 _D5mintl8sortedaa11SortedAA_ik8SortedAA15opApplyIterStepFDFKS5mintl8sortedaa11SortedAA_ik8SortedAAZiiZi 1112802 7143301 2940878 2 _D5mintl8sortedaa11SortedAA_ik8SortedAA7getNodeFiiZPS5mintl8sortedaa11SortedAA_ik8SortedAA4Node Does knowing this help me? But i can't find the equivalent methods in my code, i don't know kow to demangle them. Any help on the profiler output anywhere, or how to use it?
Sep 21 2005
parent reply "Ben Hinkle" <ben.hinkle gmail.com> writes:
"Ivan Senji" <ivan.senji_REMOVE_ _THIS__gmail.com> wrote in message 
news:dgr171$1am$1 digitaldaemon.com...
 Ben Hinkle wrote:
 Try running with profiling turned on (the -profile compiler flag). You 
 probably won't have to rebuild mintl but who knows - I haven't tried it.
 With the undefined symbols the mintl.lib is built with compiler 
 options -release -O and the mintl_debug.lib is built with -g (or 
 something like that) so which one to use depends on how you compile your 
 code. If you compile with -release then you want to link with mintl.lib. 
 Otherwise link with mintl_debug.lib.

Thanks for reply. The profiler output is very confusing.

I think thr profiler shows number of calls, total time over all calls and time spent in the function. I don't think the columns are labelled or what those different blocks are about. I agree it's not easy to figure out what the output means. See also http://www.digitalmars.com/ctg/trace.html
 Example for one of my methods:
 My version:
       1       21688        1475        1475 
 _D2lr7Grammar19calculateBEGINSWITHFZv

 Mintl(Set):
       1      107029        1404        1404 
 _D2lr7Grammar19calculateBEGINSWITHFZv

 Mintl(SortedSet):
       1       58309        1524        1524 
 _D2lr7Grammar19calculateBEGINSWITHFZv

 So i guess that my part of code in this function is doing the same thing
 but the total function takes 2-5 times longer, it uses a lot of Set!(int) 
 adding elements, cheching for elements and iterating.

The first column is number of calls, then total time, then self-time. The second column is bigger when the child functions take longer.
 When using mintl version (SortedSet) among the first 15 longes methods are 
 these:

 231237    21646605    10489211          45 
 _D5mintl8sortedaa11SortedAA_ik8SortedAA15opApplyIterStepFDFKS5mintl8sortedaa11SortedAA_ik8SortedAAZiiZi
 1112802     7143301     2940878           2 
 _D5mintl8sortedaa11SortedAA_ik8SortedAA7getNodeFiiZPS5mintl8sortedaa11SortedAA_ik8SortedAA4Node
 1112802     2224743     2070060           1 
 _D5mintl8sortedaa11SortedAA_ik8SortedAA11fixupSharedFZv
 1089386    11071788     2039195           1 
 _D5mintl3set43Set_iS5mintl8sortedaa11SortedAA_ik8SortedAA3Set7addItemFiZv
 1089386     9032592     1987612           1 
 _D5mintl8sortedaa11SortedAA_ik8SortedAA13opIndexAssignFkiZv
  356673     1977680     1299222           3 
 _D5mintl8sortedaa11SortedAA_ik8SortedAA10insertNodeFikPS5mintl8sortedaa11SortedAA_ik8SortedAA4NodeiZPS5mintl8sortedaa11SortedAA_ik8SortedAA4Node
  356673      536008      520647           1 
 _D5mintl8sortedaa11SortedAA_ik8SortedAA11insertFixupFPS5mintl8sortedaa11SortedAA_ik8SortedAA4NodeZv


 And these (when using Set):

  142939    12051752     5905363          41 
 _D5mintl6hashaa9HashAA_ik6HashAA15opApplyIterStepFDFKS5mintl6hashaa9HashAA_ik6HashAAZiiZi
 1089386     6197012     2152279           1 
 _D5mintl3set5Set_i3Set7addItemFiZv
 1089386     4044732     2075248           1 
 _D5mintl6hashaa9HashAA_ik6HashAA13opIndexAssignFkiZv
 1112802     1970573     1427748           1 
 _D5mintl6hashaa9HashAA_ik6HashAA7getNodeFiiZPPS5mintl6hashaa9HashAA_ik6HashAA4Node
   57393      327416      306849           5 
 _D5mintl6hashaa9HashAA_ik6HashAA13initDataArrayFZv
  142939    12616063      283985           1 
 _D5mintl6hashaa9HashAA_ik6HashAA44MOpApplyImpl_S5mintl6hashaa9HashAA_ik6HashAA14opApplyWithKeyFDFKiKkZiZi
  142939    12332077      280324           1 
 _D5mintl6hashaa9HashAA_ik6HashAA18opApplyWithKeyStepFDFKiKkZiiZi



 Also on the top of mintl profiler output (in the part after
 ======== Timer Is 3579545 Ticks/Sec, Times are in Microsecs ========)
 there are these two methods:

  231237    21646605    10489211          45 
 _D5mintl8sortedaa11SortedAA_ik8SortedAA15opApplyIterStepFDFKS5mintl8sortedaa11SortedAA_ik8SortedAAZiiZi
 1112802     7143301     2940878           2 
 _D5mintl8sortedaa11SortedAA_ik8SortedAA7getNodeFiiZPS5mintl8sortedaa11SortedAA_ik8SortedAA4Node

 Does knowing this help me?

 But i can't find the equivalent methods in my code, i don't know kow to 
 demangle them.

 Any help on the profiler output anywhere, or how to use it?

It looks like the foreach traversals are taking most of the time. I notice there aren't any lookups listed - just adding items and foreaching. Maybe try inlining to help the optimizer out with the foreach code. A HashAA maintains links between inserted items so foreach traversal is equivalent to a linked-list traversal. Even though implementing a set as an array is not efficient for large sets it could be that the sets you are using are small enough that the array implementation is faster even when compiling mintl stuff with -release -O -inline and everything else that could speed it up.
Sep 21 2005
parent Ivan Senji <ivan.senji_REMOVE_ _THIS__gmail.com> writes:
Ben Hinkle wrote:
 
 It looks like the foreach traversals are taking most of the time. I notice 
 there aren't any lookups listed - just adding items and foreaching. Maybe 
 try inlining to help the optimizer out with the foreach code. A HashAA 
 maintains links between inserted items so foreach traversal is equivalent to 
 a linked-list traversal. Even though implementing a set as an array is not 
 efficient for large sets it could be that the sets you are using are small 
 enough that the array implementation is faster even when compiling mintl 
 stuff with -release -O -inline and everything else that could speed it up. 
 
 

This could be the reason, int sets are usually < 20~30 elements. I am thinking of writing array based associative array to use it as Set's container. Then i'll try using Set!(Value,ArrayAA!(Value)) and see how it compares to plain array-set.
Sep 21 2005