Character matrix upgrade performance is dismal
|Created on||Nov 20, 2005 15:12|
|Resolved on||Oct 24, 2006 14:42|
|Attachments||upgradeHeapIntMat.sac, upgradeHeap.sac, upgradeChar.sac|
I'm not sure whether this counts as a Real Bug or not, but I'm going to stick it in here anyway. 1. upgradeHeap.sac is the integer vector version of APL "upgrade". Given an integer vector, V, generate a permutation vector PV, such that V[PV] is in non-decreasing order. Furthermore, PV must be stable, i.e., "upgrade 2 2 2 2 2" must produce 0 1 2 3 4. This means that heapsort (which is what this code implements) can be used, as it is stable, but quicksort can not be used. This runs about 3x faster than the APL interpreter's version of upgrade. 2. upgradeChar.sac: If we replace the integer vector argument of upgradeHeap.sac with a character matrix, and insert upgradeLT and upgradeGT to perform stupid, incorrect (due to signed char in sac) lessthen/greaterthan on character vectors, the performance of the sac code is at least twice as poor as that of the APL interpreter. I suspect the latter does not do anything special for character upgrade. 3. If I do "sac2c -O3 -dcccall UpgradeChar.sac", then insert "-pg" into syscall.sh and recompile, the generated code runs a LONG time, then dies with segmentation fault. 4. If I do "sac2c -O3 -noinl -dcccall upgradeChar.sac", then insert "-pg" into syscall.sh and recompile, the generated code runs long enough to drive me to boredom and tears. I'll go back and try again with a much smaller argument matrix and see if gprof gives any hints as to where we're thumb-twiddling. 5. Haven't tried upgradeHeap.sac on an integer matrix. That may be enlightening. Or not.
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information