From ... From: Erik Naggum Subject: Re: Waving the lambda flag again (was: Constants and DEFCONSTANT) Date: 1999/04/02 Message-ID: <3132042770550791@naggum.no>#1/1 X-Deja-AN: 461918168 References: <7dr23c$2re$1@shell5.ba.best.com> <3131961221139730@naggum.no> <4niubflwhf.fsf@rtp.ericsson.se> <41UM2.19154$134.197089@tor-nn1.netcom.ca> mail-copies-to: never Organization: Naggum Software; +47 8800 8879; http://www.naggum.no Newsgroups: comp.lang.lisp * hs@inferno.nirvananet (Hartmann Schaffer) | Actually, several steps in the evolution might be even more interesting OK, I'll do the steps thing. at issue was hacking up and printing a time representation. the naïve solution is to use a bignum of seconds since some human-inspired epoch, use FORMAT with ~D to print it. however, I also needed proper timezone support (CL's support is suitable only if you deal with times in a single timezone), and milliseconds (since a second is a really long time to modern computers, and even milliseconds are). the zone was represented as the number of hours west of Greenwich. the time representation is now split up into day, time, and milliseconds. the zone is changed to seconds eas of Greenwich. day 0 is 2000-03-01, because that's when a new 400-year leap year period starts, which means that the leap day is at the end of the four years, the centennium, and the quatercentennium, and thus no expensive computations are needed to check for leap years. however, the main culprit was division. it is an expensive operation, table lookup not, so I precomputed tables for the 146097 days of a quatercentennium and the 86400 seconds of a day, and did a nifty data representation hack so the values fit in a single fixnum. the full time representation was changed from a class to a structure, and proper declarations meant that the access functions were inlined and the type (fixnum) propagated properly. time comparison functions now compared three fixnums instead of bignums and a fixnum (milliseconds) and that meant the timezone tables (extracted from the Unix timezone database that the C library uses (but also gives you exactly one handle on)), were searched much faster. in addition, the interval of the timezone was made available to the caller upon demand (it affects the length of a local day, which can be 23, 24, or 25 hours!) and also cached, since most times decoded were in the same timezone. the time zone adjustment function also did simple addition and subtraction instead of new divisions into day and time. what really made a difference once I had figured out how to store the values in a fixnum (I'll leave that as an exercise for the reader -- since it's so far from obvious how to do it, some people will get a real kick out of how simple it is, and I don't want to take that kind of joy away form anyone), was to pass a preallocated vector for the decoding functions to store its values into instead of returning them as multiple values. finally, printing turned out to be very division-intensive, too, so I precomputed a pair of tables of high and low digits for 100 numbers. streams were also very expensive, so I deposited characters directly into a preallocated string and returned a copy or wrote it out (depending on whether the stream argument was NIL or a stream, like FORMAT). centuries were easy to change into numbers in the 16 to 99 range instead of 1600 to 9900. (granted, I have built myself a system with a serious Y10K problem, but I'll print a warning in the year 9900 if it makes anyone less worried. rumor has it that Y1K brought us the Dark Ages because it took 400 years to update all the software to four instead of three digits in the year.) the only real problem I had with tuning this stuff was that a 400 MHz CPU is damn hard to get useful statistics from every 10 ms. it manages to do a tremendous lot of work in 10 ms, so I had to let profiling run for many minutes to collect useful data as I got closer to the optimum. #:Erik