Thin Prefs

Motivation

Foswiki deals with preferences like a stack: topic preferences overrides web preferences, that override plugins preferences, and so on. Also, there are some requirements:

1. Code to get a preference value must be fast, since it's called a lot of times
2. Preferences state must be able to be saved and restored (used by INCLUDE)
3. There must be a way to take preference values from a web/topic without considering the stack (used by access control mechanism)

The current implementation isn't exactly a stack: each level corresponds to a topic/web/plugin/etc. It is done this way because of (b) above. However suppose I have a deep stack and I want a value that is defined on the first level. I'd have to search for the definition on every level! To improve performance, the current code copies all values from one level into another: the second level has the values defined on the second level plus those defined on the first. The third level copies all values from second level, including those copied from the first.

Description and Documentation

I developed a new Foswiki::Prefs based on:

• It should have at least similar performance to the current one
• As little redundant copies as possible
• It should be 100% compatible with the current (so it could be a drop-in replacement)
• It should be back-end agnostic, so it doesn't matter how the preferences are stored/loaded (flat text files that are parsed for each request, Storable on-disk cache, etc)

Here how it works:

• Foswiki::Prefs is the front-end, Foswiki::Prefs::Stack, Foswiki::Prefs::Web and Foswiki::Prefs::Parser are helpers and all other Foswiki::Prefs::* are the back-ends.
  • The front-end deals with preferences logic (supported by Foswiki::Prefs::Stack and Foswiki::Prefs::Web)
  • The back-ends deal with the way preferences are stored/loaded.
• The front-end:
  • Has a main stack and web stacks.
  • Each stack:
    • has a bitmap associated with each preference. This bitmap indicates the levels where the preference is defined
    • There is a level list: each element corresponds to a level and it's a simple back-end object
    • There is a hash that maps preferences to the level where they were finalized.
  • There is a hash that maps "$web.$topic" to back-end objects (the same as above)
    • This way I have preferences values of each topic at most once (if the back-end loads it into memory)
• The back-end:
  • Initializes itself
  • It's able to return a list of preferences defined (only the keys, not the values)
  • It's able to return a local-defined preference value ( Local, instead of Set)
  • It's able to return a preference value
  • Finalizes itself

But how can it be fast to get a value?

To simplify the example, lets suppose we are dealing with preferences stacks smaller than 8 levels. Suppose a preference map is 01011101. For this example lets assume that the rightmost bit is bit 0 (and corresponds to level 0). This preference is defined on levels 0, 2, 3, 4 and 6. We want the value from the 6th level. This bitstring, converted to a decimal number, is 93. Lets take the integer part of the logarithm of this number on the base 2: int(log2(93)) = int(ln(93)/ln(2)) = int(6.54) = 6. Hey, we got the level where the preference is defined! This rule always holds ( The mathematical proof is left as an exercise ). So, I can figure out from which level I should take the value with a simple O(1) operation. Then I ask the backend object at level 6 to give me the value I want. Note: the implementation doesn't use strings, but bitstrings

With this design it's easy to save state: it's enough to return the level index. The recover process is a bit slow and complicated (compared to the current implementation), more specifically the map: the idea is to set to 0 all bits above the level we want to restore. To achieve this I build a special bitmap that has only 1 from level 0 to the one I want to restore, then I perform a bitwise AND. Taking from our previous example: if we want to restore to level 3, then (2 ** (3+1)) - 1 = 15 = 00001111b. 00001111 & 01011101 = 00001101, that correspond to the first 4 levels.

See more details on code documentation.

This design has another interesting part: the backends. I wrote two: Foswiki::Prefs::TopicRAM and Foswiki::Prefs::HASH. The first is used to get this mechanism working without adding dependencies. The second is used to store custom settings. I could develop a Foswiki::Prefs::TopicDBM, for example, and store all preferences values from all topics in a DBM. Probably, there would be a performance gain, since preferences would not be extracted from topics for each view. The database would be updated at save time. I would have almost nothing in RAM and DBM itself uses shared memory among concurrent processes making requests. I don't know if the performance loss to get a preference would be noticeable (DBM is fast, but plain hashes are faster).

This is an improvement in code flexibility and clarity. However, the real problem with preferences is the time required to load the preferences, not the storage or post-load runtime. Each time a preference level is loaded it requires a text parse of a topic, which is slow - many, many, many times slower, and more memory hungry, than any prefs storage model. Because prefs are so intimately bound up with the Foswiki architecture, it would be really hard to do anything to improve performance that doesn't involve cacheing the values read from these topics, for example in a DB.

There are two approaches that can be taken here. The first is to take preferences out of band (store them somewhere other than in the topic text). The second is to aggressively cache the preferences read from topics.

-- GilmarSantosJr - 11 May 2009