Posted by eyarrow (eyarrow), 15 October 2003Hi,
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.
Posted by admin (Graham Ellis), 15 October 2003OK .... 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 2003Addendum 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 2003Graham,
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?
Posted by admin (Graham Ellis), 15 October 2003No, 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 .....
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 2003Graham,
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?
Posted by admin (Graham Ellis), 16 October 2003Goodness ... 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??
PH: 01144 1225 708225 • FAX: 01144 1225 899360 • EMAIL: firstname.lastname@example.org • WEB: http://www.wellho.net • SKYPE: wellho