OPT requirements

Zyx — Sun, 06 Apr 2008 10:28:00 +0200

I've found a new entry on the bugtracker recently. The author informed that he gets "Nesting level too deep - recursive dependency" error while running the development examples provided by the newest OPTv2 dev version. I looked at it deeper and found out that he lowered the default nesting level limit 4 times from 64 to just 16. Obviously, this is a quite drastic change and would affect not only OPT, but many other scripts as well. However, I think it is time to take a look at the OPT issues concerning the requirements, because several of them needs a deeper explaination.

The optimizations implemented in OPT, mostly concern the main parser class and the compiler. The first one is the part that is loaded every time the script wants to use templates, so it must provide huge quality standards. There are no sophisticated algorithms, so the speed improvements are:

To minimize the size of the code.
To minimize the amount of points that try to access the hard drive.
To use the fastest elements of the language.

The point is this class must be as light as possible; I would even say: almost transparent for the script.

The situation is quite different, when it comes to the compiler. It is loaded from time to time, so it can be big and splitted for more files (of course without exaggeration). The key role is played by the limits set in the PHP configuration, because in the pesimistic situations, the compiler runs out of resources to complete the task. Unfortunately, some of the new features cost a lot, and if the users wanted XML tag parsing, they must face the consequences: every such tag requires its own node object in the document tree and they need some preparation tasks to be done. My role is to minimize the time and memory necessary to do this.

The elements that can be exhausted during the compilation are:

The stack
The memory

The algorithms used in the compiler operate on a data structure called tree, and the use lots of recursion. It consumes the stack, because the number of currently executed methods and functions grows quite fast. In PHP, the default limit for the stack depth is 64 and if you are going to use OPT, the worst you can do is to lower it to ridiculous values like "16" that would affect not only OPT, but also many other scripts :). However, every recursion has an imperative version, constructed for example by queues. Maybe it does not consume less memory, but at least it does not depend on the limits. Such changes have been applied to many compiler methods so far, but some of them still require my attention, because they are not so trivial:

Processing the tree by the instruction processors
Expression compilation

In the first one the situation is clear: we get a node of some instruction and want to process it. We find its processor and redirect the node to it. It generates some PHP code and decides, what to do with its children. By default, it wants to process them, too. Here comes the recursion and the process starts from the beginning. There are some difficulties. The algorithm is split over many classes, and the programmers may create their own. What is more, some instructions need to start the subnode processing immediately, because their next decision depends on the code generated by the children. Obviously, this eliminates queues. An elegant replacement could be made, if we had an access to the low level programming.

Let's take a look, how it affects the compilation process. We have a huge template, with the tags nested up to the level 30. OPT with the compiler can take another 10 calls, and in the deepest place we have a complicated expression with brackets. To sum up, the library uses approx. 45 calls from 64 available, which is more than 70% of the limit! I know this case is quite pesimistic and in normal life such HTML documents are very rare, but it shows, how demanding the compilation can be.

If we can't remove the recursion without ugly tricks which would be never accepted by the instruction authors, how we can get around it? The idea is not to remove recursion completely, but we keep it in some places. I use here the fact that the immediate access to the subnode compilation results is necessary only for some instructions, and for example the HTML tags do not need it at all. If we get a random node from the tree, we have a big chance that it would not need a recursion here. So, why don't we provide a dual version of this algorithm? By default, it is executed with a queue, but for more sophisticated needs, some nodes can switch it to recursion. Now it can happen that a tree with a depth 30 is processed in one single loop, with no recursion! I predict that in normal situations, the algorithm will consume only 3, 4 spare "items" in the stack, which is fully acceptable.

The second issue concerns the memory usage. It's not so tragic here, but we can notice a significant rise when compared to the OPT 1.x compiler, even with using some patents from that version. The most memory is consumed by the tree. I've measured some single nodes recently and the results were from 2 kilobytes for a single node to 3 kilobytes for a node with one attribute. When the instructions start to add the PHP code to the buffers, the things are getting worse, but it happens only in some nodes in the whole template. We can safe some memory here. The objects use various arrays, which are initialized just in the beginning, for example:

abstract class optScannable extends optNode implements Iterator
{
	protected $subnodes = array();

In most of the nodes, the arrays are empty, so it it no sense for them to exist all the time. I fixed the code so that it creates an array only when it is necessary. From the declarations, the = array() parts were removed. The effect is quite interesting. On a single array, we safe 400 bytes. The new results are:

Single node with no attributes: 1400 b.
Single node with one attribute: 2350 b.

The additional memory may be safed by releasing the huge data that will not be used anymore, for example the template content.

What do we have to remember, while using the new OPT, when it comes to the requirement issues:

With the terribly low limits, the compiler will always crash. I thing 16 megabytes for the script (the default limit) is big enough both for the compiler and the script.
The best place to run the template parsing is the end of the script. We can delete some unncessary data earlier to free some memory.
The templates using the inheritance are more demanding, especially when overwriting snippets, because the compiler must keep also the old versions in the memory.
The quirks mode will consume less memory (simpler tree - no XML tags), but it is not implemented yet.
The compilation is run once for a long time. During the normal execution, we can forget about the limit issues etc.

I think this note shows, how difficult the library creation can be. The key is to know, what we can use in current place and that there is also the rest of the script which uses the same memory and has its own requirements.

OPT 2.0.0-dev5

Zyx — Fri, 21 Mar 2008 14:38:00 +0100

The new development version became available a bit later that I planned, but on the other hand, I managed to add much more new things. The DTD issue is solved, as well as XML prologs, CDATA support and code escaping. The expression compiler is done and the programmers may use now brand new component implementation. This is a significant step towards the first beta release and the end is closer than further. There are only a few instructions to code, the rest is almost completed and works. The compiler, programmers' API and most of the stuff also works. I think of making the first real tests on my home website and creating the Open Power Forms library compatible with the new OPT.

In the new OPT, I've redesigned the component design from scratch. It is much more flexible now and allows to make easily many interesting effects. The base rules are still the same, but the rest has changed. This is a sample code showing, how the component-based work with the forms is going to look like:

<opt:snippet name="componentView">
  <com:div class="field" invalid="field error">
    <p>{$opt.component.title}: <opt:display /></p>
    <p class="desc" opt:if="$opt.component.description">{$opt.component.description}</p>
    <opt:onEvent name="error" message="info">
      <p class="error">{@info}</p>
    </opt:onEvent>
  </com:div>
</opt:snippet>

<div class="form">
<form method="post" action="skrypt.php">

<opt:input name="name" template="componentView">
   <opt:set name="title" str:value="Enter your name" />
   <opt:set name="description" str:value="At least 3 letters" />
</opt:input>

<opt:input name="surname" template="componentView">
   <opt:set name="title" str:value="Enter your surname" />
   <opt:set name="description" str:value="At least 3 letters" />
</opt:input>

<opt:input name="age" template="componentView">
   <opt:set name="title" str:value="Enter your age" />
   <opt:set name="description" str:value="Scope: 10-99 years" />
</opt:input>

<div class="foot"><input type="submit" value="Send" /></div>
</form>
</div>

The new implementation makes use of the opt:snippet instruction and template inheritance. If you had enough time, you might code the component objects, so that the field titles and descriptions will be unnecessary in the template. A component can handle events, displaying itself and its neighbourhood, managing parameters and tag attributes (we use the com namespace for it). OPT contains only the component mechanism, and the components itself must be written by the end user. The reason is very simple. In order to make a useful component, we should integrate it with the input validation classes, language system, error management etc. The demands are much bigger than OPT is able and is supposed to provide. However, there will be a ready-to-use component implementation: Open Power Forms library.

Unfortunately for the English manual is not started yet. Even the Polish users must use a partially-complete text, without formatting, because the new rendering system is not ready. However, we'll do everything to translate all the text together with some other materials (advices, FAQ, maybe even a tutorial?) into English, before the first final release is done. There is a team, I'll try also to ask some friends and we'll make a serious English support. Just be patient.

Download OPT-2.0.0-dev5

Invenzzia... in English - opt2

OPT requirements

OPT 2.0.0-dev5