From: ptkwt@...1.aracnet.com (Phil Tomson) Date: 2003-01-12T05:48:55+09:00 Subject: Re: Why is the performance of list_append O(n**2)? Ooops... following up to my own post again.... In article , Phil Tomson wrote: >In article <3E1FF274.2090106@pssw.NOSPAMPLEASE.com.invalid>, >Louis Krupp wrote: >>The problem: Read a structured file (the details are irrelevant) >>and generate a program which, when run, would produce the original >>file. Modify the program, re-run it, and you have a relatively >>easy way to change the original structured file. > >>For various reasons, C++ seemed like the way to go when I first did >>this. It worked, until I was handed structured files that were 4 MB >>long and the generated C++ program went on for some 600,000 lines >>and g++ crashed trying to compile it. >> >>I needed a scripting language. I should have realized that a long >>time ago. >> >>I tried Ruby. Ruby had a political advantage: It wasn't Perl. >>The problem with Perl was that it's been around long enough to have >>a reputation, deserved or not, for being hard to read. I don't >>mind Perl, but my boss was visibly relieved to hear I was using >>something else. >>I wrote a Ruby script generator that worked for small input files. >>It worked for large input files, too, but it was slow, very slow. >>It took 18 minutes to reproduce a 4 MB structured file. My >>generated C++ program couldn't do it at all, but 18 minutes was >>still too long. >> >>When I took a closer look, I realized that most of those 18 minutes >>were spent parsing the script, and most of that time was spent in >>list_append. >> >>The problem, I finally figured out, was the arrays. The generated >>script had lots of them, and many of them were big, some with more >>than 10,000 elements. > >> >>list_append (from 1.6.8) looks like this: >> >>--- >>static NODE* >>list_append(head, tail) >> NODE *head, *tail; >>{ >> NODE *last; >> >> if (head == 0) return NEW_LIST(tail); >> >> last = head; >> while (last->nd_next) { >> last = last->nd_next; >> } >> >> last->nd_next = NEW_LIST(tail); >> head->nd_alen += 1; >> return head; >>} >>--- >> >>Following nd_next links for each of n array elements takes >>O(n**2) time. > >Yes, that does seem excessive... > >>A tail pointer would have been useful, but with >>the node structure being as compact as it is, there was no room >>for one. >> >>Desperate times called for desperate measures. I don't expect >>anyone to like what I did. I'm not crazy about it myself. >> >>I added another word to the node: >> >>--- >>typedef struct RNode { >> ... >> union { >> struct RNode *node; >> } u4; >>} NODE; >> >>... >> >>#define nd_tail u4.node >> >>... >> >>static NODE* >>list_append(head, tail) >> NODE *head, *tail; >>{ >> NODE *last; >> >> if (head == 0) return NEW_LIST(tail); >> >> if (head->nd_tail) { >> last = head->nd_tail; >> } else { >> last = head; >> } >> >> head->nd_tail = last->nd_next = NEW_LIST(tail); >> head->nd_alen += 1; >> return head; >>} >>--- >> >>It worked. The monster script that generated 4 MB of structured >>stuff ran in under six minutes instead of 18. This is almost >>acceptable, and it's a lot better than a g++ compilation that >>takes 15 minutes to not work at all. >> >>My immediate problem seems to be solved, but I don't want to make >>my company dependant on a patched version of Ruby forever, so I'd >>like some feedback. >> >>I can see this going one of several ways: >> >>1. Array parsing should be improved. Adding a word to the node >>structure is crude and unimaginitive, but it may be necessary. >> >>2. Array parsing should be improved, and there's a better way >>to fix it than by bloating the node size by 33%. >> >>3. Array parsing could be improved, but don't expect it to >>happen any time soon. If you insist on having 10,000-element >>arrays, you might consider finding another language. Actually, I would hope the answer isn't 3 - I think cases like yours might help us improve performance. >> > >You mean appending to the end of an Array should be improved, am I >right? Actually, now I relize you're talking about list_append in the parser (parse.h, parse.c) not in the Array class... You're talking about arrays that the parser builds, not Ruby Arrays (am I right?) > >It certainly seems that the O(n**2) performace for appending an item to >the end of an Array could be improved upon. Why would each node in the list >have to carry around the tail info? Why couldn't we do it so that Array >object (as defined in C, of course) always knows where it's tail is? Then >you only add the overhead of one pointer for the whole array (unless I've >misunderstood what you did). Of course you add some time overhead >whenever the array grows or shrinks, but I don't think a new pointer >assignment adds much time. > >Or perhaps since we always know how many elements are in an Array (don't >we, I haven't looked at the Array C code, I hope we don't do a n**2 >traversal to find out) couldn't that info be used by list_append? > >> >>Thanks for taking the time to read this. >> > >I changed the title of this thread so as to get the attention of Ruby >internals folks (matz, guy, are you listening? :) Can the parser be improved in this case? Phil -- "Or perhaps the truth is less interesting than the facts?" Amy Weiss (accusing theregister.co.uk of engaging in 'tabloid journalism') Senior VP, Communications Recording Industry Association of America