Training, Open Source computer languages
PerlPHPPythonMySQLApache / TomcatTclRubyJavaC and C++LinuxCSS 
Search for:
Home Accessibility Courses Diary The Mouth Forum Resources Site Map About Us Contact
Tcl Arrays

Posted by eyarrow (eyarrow), 15 October 2003
Hi,

I have written a process, that in real time calculates 10 levels of order book depth for a particular instrument on a particular stock market.

Although TCL is not ideal for this task... there ya go - that what I have to use.....

I am utilising sorted arrays to do the bulk of the work ... but do not understand how the ascend/descend sort works at a processing level. How efficient is it? Does it use caching?

Basically - we need to purchase a new Sun UNIX box in order to get the process running - and would like to know whether we can improve perfomance using Cpu caching for instance.

Many thanks

Elliot

Posted by admin (Graham Ellis), 15 October 2003
OK .... you don't sort an array, you sort a list.   The list can be a list of keys to the array ....

Efficiency rule number one - filter your list to exclude unwanted items before you sort it.   If you have 100 keys but only want to report on (say) 10 of them, you'll cut the sorting effort by a factor of about 30 if you exclude then sort, rather than sort then exclude.   I think (90% sure) that the algorithm used is Quicksort, which performs roughly n log (n) comparisons per sort, where n is the number of records being sorted.  Thus:
* 10 items to sort, and you have roughly 25 comparisions
* 100 items to sort, and you have roughly 460 comparisons
* 1000 items to sort, and you have roughly 6900 comparisons.

I was in Oxford yesterday, and I picked up a book - "Programming Pearls" by Jon Bentley - which has 5 or 6 pages on quicksort; so new to our library that we haven't got it on line yet, but I'll follow up this post when we do have it up.

Tcl's lsort routine takes a "-command" option, and you might find it very instructive to write your own sort proc to differentiate between two records rather than use the default proc;  that way, you could add a puts into the sort proc for experimental purposes, and see just how much work is being done.   I've found this a very useful technique.

You ask about caching;  if you have a complex sort routine under -command, there's nothing to stop you writing code to cache the work done to ananlyse the records your sorting, and once again this can lead to big efficiency savings - I have done this on sorting IP addresses, and halved the time taken to sort!

Final thought - are your sorts "incremental"?  In other words, do you sort a number of records, then add in one or two to the set, take one or two out, and sort again?   If you do, storing the keys in a tree or using some other technique will save a lot or repeated work.

I've probably given you some food for thought here, though perhaps not fully provided you an answer quite along the lines you were asking; hope the answer helps.   Please do post up some more "metrics" of the problem if you would like some further guidance.  Tcl is a scripting language and it's never going to be hyper-efficient;  there are warnings about a drop off in efiiciency in handling long lists in older releases, but I think these have largely been dealt with now.  In an extreme situation, you could add in a sort routine in "C" - after all, Tcl is first and foremost a C library  

Posted by admin (Graham Ellis), 15 October 2003
Addendum to previous post - "Programming Pearls" is described at http://www.wellho.net/book/0-201-65788-0.html and there's a link from that page to Amazon (Uk and / or USA, depending on your country) if you want to order a copy  

Posted by eyarrow (eyarrow), 15 October 2003
Graham,

Another quick question... does lsort use a bubble sort / insertion sort technique?

I have been looking for the source code for this function ... I wondered whether a divide and conquer tenchnique would work more efficiently?

Thanks inadvance

Elliot


Posted by admin (Graham Ellis), 15 October 2003
No, I don't believe it uses a bubble sort; I would hazard (90% sure) that it's a form of  quick sort.   The sure fire way to test it is to use the -command option to provide a comparator, and print out some traces from within there ... in fact .....

Code:
proc which {first second} {
       global counter
       incr counter
       puts "Comparing $first to $second"
       if {[string length $first] < [string length $second]} {return 1}
       if {[string length $first] > [string length $second]} {return -1}
       return 0
       }

set counter 0
puts [lsort -command which {one two three four five six seven eight nine ten eleven twelve}]
puts "Count was $counter"


Which ran:

Code:
[localhost:~] graham% wish ww
Comparing one to two
Comparing three to four
Comparing one to three
Comparing one to four
Comparing five to six
Comparing seven to eight
Comparing five to seven
Comparing five to eight
Comparing three to seven
Comparing four to seven
Comparing four to eight
Comparing four to five
Comparing one to five
Comparing one to six
Comparing two to six
Comparing nine to ten
Comparing eleven to twelve
Comparing nine to eleven
Comparing nine to twelve
Comparing three to eleven
Comparing three to twelve
Comparing three to nine
Comparing seven to nine
Comparing eight to nine
Comparing four to nine
Comparing five to nine
Comparing one to nine
Comparing one to ten
Comparing two to ten
Comparing six to ten
eleven twelve three seven eight four five nine one two six ten
Count was 30
^C
[localhost:~] graham%


Yep - about the number of comparisons I expected, and the sort of figure that can't be much improved on if you don't know the pattern of the incoming data.    If you have two sets of incoming data that you need to merge, that's a whole different ballgame - you could then, as you suggest, divide and conquer.

[Added later - I've a feeling looking at comparison order this may actually be a form of shell sort rather than quicksort; it's a long time since I studied sort algorithms.   Whichever, I don't think you'll get the number of tests down on data that comes in "random"]

Posted by eyarrow (eyarrow), 16 October 2003
Graham,

Funnily enough, following your first reply - I had insitigated such a proc - and had been drawn to the same conclusions.

With the nature of market data, I do not think we can beat a quick sort algorithm - although I did consider the possibilities of re-writing all ten records per instruments into "sub-schemas" for quicker comparison. However, I feel maintaining for instance  5 pairs of numbers per instrument would indevitably add to the work load prior to writing the record to disk.

One question I do have - is relative to hardware. Should we go from an 8cpu Sun box onto a 4 cpu Sparc 3 chipset box, with 1MB cpu caching - would we witness an increase or decrease in performance. I.e. can tcl utilise cpu caching in this instance?

Many thanks

Elliot

Posted by admin (Graham Ellis), 16 October 2003
Goodness ... on the hardware, any advice I gave would be a guess and wouldn't be worth the bandwidth taken up to transmit it .... sorry about that;  I'm really not "into" Sun's cpu cacheing ....

If it's that important to know, and you're going to be placing a juicy order, could you ask for a benchmark to be run??



This page is a thread posted to the opentalk forum at www.opentalk.org.uk and archived here for reference. To jump to the archive index please follow this link.

You can Add a comment or ranking to this page

© WELL HOUSE CONSULTANTS LTD., 2014: Well House Manor • 48 Spa Road • Melksham, Wiltshire • United Kingdom • SN12 7NY
PH: 01144 1225 708225 • FAX: 01144 1225 899360 • EMAIL: info@wellho.net • WEB: http://www.wellho.net • SKYPE: wellho