digitalmars.D.dtl - mintl.Set help please
- Ivan Senji (21/21) Sep 18 2005 I decided to replace my own stupid set in some projects with
- Ivan Senji (9/18) Sep 18 2005 I now added
- Ivan Senji (54/57) Sep 18 2005 There was a mistake elsewhere in code.
- Ben Hinkle (9/26) Sep 18 2005 By default Set is implemented as a hashtable so you need to override toH...
- Ivan Senji (17/55) Sep 18 2005 Just replaced Set!(A) with SortedSet!(A) and it works! Just one more
- Ben Hinkle (5/24) Sep 18 2005 cool! Thanks for giving it another chance.
- Ben Hinkle (6/27) Sep 18 2005 wierd. It looks like dmd needs more help in figuring out when to define ...
- Ivan Senji (22/22) Sep 20 2005 I have replaced my Set class with the one in mintl and
- Ben Hinkle (9/31) Sep 20 2005 Try running with profiling turned on (the -profile compiler flag). You
- Ivan Senji (57/65) Sep 21 2005 Thanks for reply. The profiler output is very confusing.
- Ben Hinkle (16/80) Sep 21 2005 I think thr profiler shows number of calls, total time over all calls an...
- Ivan Senji (6/17) Sep 21 2005 This could be the reason, int sets are usually < 20~30 elements.
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
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_mintl1AI 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
Ivan Senji wrote:Ivan Senji wrote:and now it links but i get: Error: illegal add argumentThere 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
"Ivan Senji" <ivan.senji_REMOVE_ _THIS__gmail.com> wrote in message news:dgjq3j$2hlp$1 digitaldaemon.com...Ivan Senji wrote: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).Ivan Senji wrote:and now it links but i get: Error: illegal add argumentThere 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.
Sep 18 2005
Ben Hinkle wrote:"Ivan Senji" <ivan.senji_REMOVE_ _THIS__gmail.com> wrote in message news:dgjq3j$2hlp$1 digitaldaemon.com...Thanks. I figured it out after i posted the question.Ivan Senji wrote: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.Ivan Senji wrote:and now it links but i get: Error: illegal add argumentThere 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.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> no problem - I'm glad to hear someone trying it out.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.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.no problem.
Sep 18 2005
"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
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
"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
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
"Ivan Senji" <ivan.senji_REMOVE_ _THIS__gmail.com> wrote in message news:dgr171$1am$1 digitaldaemon.com...Ben Hinkle wrote: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.htmlTry 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.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
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