Work in progress - better list processing

The current list traversing functions in XEmacs, like Fmemq, have a few problems relating to circular list checking. The use of the QUIT macro in each loop iteration allows the user to get out of an infinite loop. This accesses a global volatile variable, and since modern processors are `I/O-bound', this is a significant performance hit. How much, you ask? I actually benchmarked this, and the numbers are between 20% and 40%, depending on processor and compiler. Your mileage will vary, but Linux users will probably see a 25% win on ALL list traversing functions. The other problem is relying on the user to explicitly abort an infinite loop. Better is to signal a circular-list error. The algorithm I use is tortoise/hare with head start. The hare is doing the normal work of the loop. After a thousand iterations, we suspect there might be a circular list, so we start up the tortoise. The only overhead for `normal' lists is integer increment and comparison with a constant, which is `free' on today's processors. While I was at it, I fixed XEmacs to not lock up when printing a circular list. DON'T TRY THIS ON YOUR CURRENT XEMACS: (progn (setq x '(nil)) (setcdr x x)) ==> (nil ... <circular list>) Martin