Hi, Folks. I have been reading the mails about sorting issues in GTK-G, and have sent an email to Emile offering to help resolve some of the problems.
I did some research some years back on the speed of the various sorting routines, under various conditions, and it turns out that the quicksort (qsort) routines are just about the very worst possible choice when trying to sort an already-sorted or almost-sorted list of items, because of the tremendous amount of recursion involved. Qsort recurses once for each already-sorted element, in an N:M way, resulting in very long sort times for even a few thousand elements, and also pushes a large amount of data on the stack for each recusion. As a result, it is slow, and uses a hugh amount of stack space, often resulting in memory fragmentation as additional stack space is allocated. I have offered to write a shell sort routine that will increase performance by at least a factor of 2 in these cases, which accepts the same parameters as the qsort, and which could be simply plugged in place of the qsort when appropriate. I'm waiting to hear from Emile, to see if he wants the help. But considering the speed of the processors most of us use these days, I can't imagine any sort that we would need to do taking enough time to show a perceptable delay on-screen, if we do it correctly. I'm hopeing to help in this regard, if the help is needed. I find that I often sort search results a number of times, to see what clusters the results I am after in the best way for me to evaluate them. I suspect that in some cases, I reverse-sort an already sorted list, which would cause qsort to give it's absolute worst performance, requiring a level of recursion for every element in the list. If we are actually inserting and removing the GTK elements during the sort, that would certainly be very, very slow. I suggested that perhaps we abstract the data during sorting, so that no GTK calls need be used during the sorting, and that once the sort is complete, then we manipulate the GTK data, by either creating a new list based on the sorted keys, or do the actual swaping of data items in the existing GTK structures after the sort is complete. This would be a possible way to speed up the sort of display data by another factor, and would hopefully result in almost instant updates of the display when sorting. I'm basing my guesses on the GTK-2 libs, and a dual-processor P-III @ 1GHZ, so you folks with nice and fast P-4 chips should see even better performance. While I'd love to use assembler code for the sorts, which would give us another factor of 2 or more speed increase, it's not possible to make that portable. And today's compilers are pretty good at generating tight code. So lets see what we can do about this. For those of you interested, the mathematical data came from Knuth's 'Art of Computer Programming', volume 3, which covers most of the common sorting and searching routines, and the math behind them. If you have never seen this book, check it out - it's been the 'programmer's bible' for about the last 10 years, no matter what language you program in. Most libraries have a copy of the set of volumes, or can get them for you as a reference book. Regards, --Carl __________________________________ Do you Yahoo!? Yahoo! SiteBuilder - Free web site building tool. Try it! http://webhosting.yahoo.com/ps/sb/ ------------------------------------------------------- The SF.Net email is sponsored by EclipseCon 2004 Premiere Conference on Open Tools Development and Integration See the breadth of Eclipse activity. February 3-5 in Anaheim, CA. http://www.eclipsecon.org/osdn _______________________________________________ Gtk-gnutella-devel mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/gtk-gnutella-devel
