Digital Mars - digitalmars.D.dtl - mintl.Set help please

↑ ↓ ← → 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

↑ ↓ ← → "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

↑ ↓ ← → 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

↑ ↓ ← → "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

↑ ↓ ← → "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

↑ ↓ ← → 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

↑ ↓ ← → "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

↑ ↓ ← → 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

↑ ↓ ← → "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

↑ ↓ ← → 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