[mercury-users] Destructive list operations

[Michael Day]

Hi Ralph,

> Once you go down this path, an array will be much faster than a list.

Yes, it turns out my map_replace is insufficiently general, as OpenType 
substitutions that perform glyph replacements also need to look ahead 
and look behind, which is not easy to do with a list.

> I'm making the following assumptions:
> - you want efficient left-to-right traversal;
> - you want efficient substitution of subranges;
> - you're not too worried about the efficiency of random access (or you
>   wouldn't be starting with lists).

All of these are valid, but there is also the need for look ahead and 
look behind, which effectively requires random access, or a double 
linked list. A double linked list also has the advantage of being able 
to easily splice things in half way.

For now, we've achieved our short-term optimisation goals by adding fast 
paths to code around the slow bits when they aren't necessary, and 
improving other areas, but ultimately we will need to swap lists for 
arrays or double linked lists. That's going to be a huge job, as there 
is so much code that is written in terms of list manipulation.

By the way, the --optimize-constructor-last-call flag allows us to drop 
a lot of the reverse-accumulator tricks we were using and get a speed 
boost into the bargain. It's great! But it doesn't seem to be enabled by 
default for -O5, is that correct? Is there any reason why it wouldn't be 
enabled for this optimisation level? It seems pretty useful; we only 
didn't use it in the past because it made the 2006 compiler crash.

Cheers,

Michael

-- 
Print XML with Prince!
http://www.princexml.com
--------------------------------------------------------------------------
mercury-users mailing list
Post messages to:       mercury-users at csse.unimelb.edu.au
Administrative Queries: owner-mercury-users at csse.unimelb.edu.au
Subscriptions:          mercury-users-request at csse.unimelb.edu.au
--------------------------------------------------------------------------