Adobe Open Source Wiki - New pages [en]

ABI safe library theory of operation

2009-08-27T23:59:08Z

Summary:

The idea with the ABI safe library (currently the version_1 namespace types) is to provide a set of types that have a defined binary representation regardless of compiler settings, version, or options. And so these types can be passed freely across a DLL boundary.

The template types are intended to be ABI safe so long as they are themselves instantiated with an ABI safe type.

The following are the specific techniques that the library uses:

1) Memory allocation - any heap allocated object will carry with it an capture_allocator (look up the actual type name). This allocator holds a pointer to a new/delete pair of proc pointers. All allocations go through the allocator and all frees also go through the allocator. This ensures that a consistent new/delete pair is used if a DLL or application of locally replaced these operations.

1a) The memory allocators in the ABI safe containers are copied with the pointers which were allocated by them. With STL containers it is undefined if the allocator is copied with the container, this means that the capture_allocator is not guaranteed to work with containers other than the version_1 containers.

2) Alignment - the types all try to ensure maximal alignment of types where necessary - this is usually done by aligning to the natural alignment for the type up to 64 bits (there may be issues with types that require 128 bit alignment). There is currently a known issue here with close_hash_map which relies on adobe::pair but makes no attempt to ensure alignment of the second element. So far this hasn't caused any real world problems and it should be fixed at some point by trying to ensure that the current "typical" alignment is kept.

3) No use of C++ compiler constructs, such as RTTI and v-tables which don't have a defined representation. Instead there is an adobe typeinfo system that relies on matching by name (rather than by a symbol that would need to be exported) and constructing v-tables with tables of proc-pointers (compiler generated as static structs - see any_regular_t).

Debugging any regular t and short names

2009-02-11T21:45:26Z

Summary:

Debugging the any_regular_t type can be problematic if you don't know what the data type of the value stored in it is. To make it simpler for to view an any_regular_t in the debugger, release 1.0.41 contains a four character short name for the type which is stored at the top of the vtable.

The structure of an any_regular_t is a pair of doubles, the first word of the first double contains a pointer to a vtable.

{| border="1"
|+ any_regular_t
|-
! colspan="2" | double || double
|-
| vtable* || pad (on 32 bit machines) || data or data*
|-
|}

The first word of the vtable contains a version number on release builds (currently 1) and a short name (a four character constant) on debug builds.

{| border="1"
|+ vtable
|-
| version or short name
|-
| ... proc pointers ...
|-
|}

By convention, the four character codes are stored in little endian order (so as to be readable in the debugger when viewing memory) -

{| border="1"
|+ short name for adobe::version_1::dictionary_t
|-
| 'd' || 'i' || 'c' || 't' || (remainder of word is zeros on 64 bit machine)
|-
|}

Also by convention, ASL will only use lower case letters in their short names - clients are free to use upper case letters. Note that the short name facility is to aid debugging _only_. it is not intended as a unique name for every type.

You can define a name for your own type using the ADOBE_SHORT_NAME_TYPE() macro in the global scope defined in <adobe/typeinfo.hpp>. For example:

<pre>
namespace my_space {
class my_class { };
} // namespace my_space

ADOBE_SHORT_NAME_TYPE('M','y','C','l', my_space::my_class);
</pre>

Once defined, a short name for a particular type can be referred to using the short_name type function:

<pre>
cout << adobe::short_name<double>::value;
</pre>

The following is a list of the short names for the CEL types defined in ASL:

{| class="wikitable sortable" border="1"
|+ CEL short names
|-
! type || name
|-
| double || dble
|-
| bool || bool
|-
| empty_t || emty
|-
| array_t || arry
|-
| dictionary_t || dict
|-
| string_t || strg
|-
| name_t || name
|-
|}

In addition, the following short names are defined though these won't typically appear in an any_regular_t:

{| class="wikitable sortable" border="1"
|+ short names
|-
! type || name
|-
| string16_t || st16
|-
| float || flot
|-
| int || int_
|-
| short || shrt
|-
| long || long
|-
| unsigned int || uint
|-
| unsigned short || ushr
|-
| unsigned long || ulng
|-
| char || char
|-
| signed char || schr
|-
| uchar || uchr
|-
|}

PropertyModelEvaluator

2008-10-29T21:32:42Z

Summary:

<pre>
Usage: pmeval [option]... [file]...
Command line only options:
--help produce help message
-v [ --version ] print version string

Grammar:
translation_unit = [ adam_test ].
adam_test = sheet_specifier [ interaction_list ].
interaction_list = interaction [ interaction_list ].
interaction = update_decl | reinitialize_decl
| dump_decl | check_decl | print_decl | assert_decl
| contributing_decl | trailing_comment | .
update_decl = "update" dictionary.
reinitialize_decl = "reinitialize" dictionary.
dump_decl = "dump".
check_decl = "check" dictionary.
print_decl = "print" "(" expression ")".
assert_decl = "assert" "(" expression ")".
contributing_decl = "contributing".

keywords += "update" | "reinitialize" | "check" | "dump" | "print"
| "assert" | "contributing" .
<pre/>

All About Binding

2008-08-22T22:57:20Z

Summary: /* Introduction */

== Introduction ==
Within a layout description, <code>bind</code> arguments are used to specify cells within the sheet to bind the widget to. The value of a bind argument must be of type <code>name</code>. A common misconception with the <code>@cell</code> notation is that <code>@</code> is some kind of reference operator - it is not. The <code>@</code> operator is a quote operator which quotes a keyword or identifier and generate a <code>name</code>.

[[Image:bind_01.png|frame|Model-View-Controller]]

The sheet within ASL acts as a model in a Model-View-Controller pattern. A typical widget, such as a checkbox, acts as a View-Controller.

[[Image:bind_02.png|frame|checkbox(bind: @cell)]]

In this configuration the widget is displaying the current value in the cell to which it is bound, and when clicked on, requests a change of the model to a new value. A control will be disabled if changing the value of the cell to which it is bound will have no effect on the output of the sheet.

Not all widgets comprise both a controller and view. A widget which simply displays a value is only a view, a piece of static text may be neither.

The usual configuration for a button is a bit different. A button binds to a cell as a view, even though it doesn't display the value. The value it binds to are typically the arguments to an action. Clicking on the button will invoke the action with the value from the cell to which the button is bound. A button will be disabled if the value in the cell to which it is bound is <i>invalid</i>. A cells value is invalid when it is derived from information contributing to an invariant in the sheet.

[[Image:bind_03.png|frame|button(bind: @cell, action: @do_it)]]

A button may also act as a controller. This is the equivalent of a button with an action that simply sets a cell within the sheet. The cell to set is specified with the <code>bind_output</code> argument. For example, let's say that you wanted a button which added 11 to the <code>value</code> cell. That could be expressed as:

<pre>
// -- in the sheet
interface:
value: 1;
output:
next_value <== value + 11;
// -- in the layout
button(name: "Next Value", bind: @next_value, bind_output: value);
</pre>

[[Image:bind_04.png|frame|button(bind: @cell, bind_output: @another)]]

The button acts as the latch in the system to prevent this configuration from being an infinite loop.

The value of a button can also be specified with the <code>value</code> argument, rather than <code>bind</code>. For example, a button which reset the above value to 1 would look like:
<pre>
button(name: "Reset", value: 1, bind_output: @value);
</pre>

Such a button acts strictly as a controller.

Performance/Analysis/Example3

2008-07-21T01:46:23Z

Summary:

<h2>Stepanov Abstraction with MSVC</h2>

Now we'll examine the results from stepanov_abstraction.cpp compiled with Microsoft Visual C++ (<b>MSVC</b>) 2008 and 2005.

And to be specific:
<pre>
Intel Core2 QuadCore 2.66Ghz
Windows Vista 64 bit Ultimate

MSVC 2008:
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 15.00.21022.08 for 80x86

MSVC 2005:
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 14.00.50727.762 for 80x86
</pre>

<pre>
cl /nologo /Ox /TP /EHsc /D "WIN32" /D "NDEBUG" /Wp64 stepanov_abstraction.cpp -o stepanov_abstraction.exe
.\stepanov_abstraction > stepanov_abstraction_msvc2008.txt
</pre>

<hr>
<h2>MSVC 2008</h2>

<h3>Accumulate</h3>
<pre>
test description absolute operations ratio with
number time per second test0

0 "double pointer" 4.60 sec 869.19 M 1.00
1 "double pointer_class" 4.59 sec 872.22 M 1.00
2 "DoubleValueWrapper pointer" 4.54 sec 881.06 M 0.99
3 "DoubleValueWrapper pointer_class" 4.55 sec 878.16 M 0.99
4 "DoubleValueWrapper10 pointer" 4.57 sec 875.08 M 0.99
5 "DoubleValueWrapper10 pointer_class" 4.54 sec 881.25 M 0.99
</pre>

This is good. The compiler had no significant penalty for increasing the data or pointer abstractions in the accumulation loops.

<h3>Insertion Sort</h3>
<pre>
test description absolute operations ratio with
number time per second test0

0 "insertion_sort double pointer" 0.86 sec 2.33 M 1.00
1 "insertion_sort double pointer_class" 1.19 sec 1.69 M 1.38
2 "insertion_sort DoubleValueWrapper pointer" 1.19 sec 1.69 M 1.38
3 "insertion_sort DoubleValueWrapper pointer_class" 1.56 sec 1.28 M 1.82
4 "insertion_sort DoubleValueWrapper10 pointer" 1.17 sec 1.71 M 1.36
5 "insertion_sort DoubleValueWrapper10 pointer_class" 1.56 sec 1.28 M 1.82
</pre>

This isn't so good -- all of the times should have been the same and the ratios close to 1.0.
Increasing the abstraction on the value and the pointer both appear to cause slowdowns.

<h3>Quicksort</h3>
<pre>
test description absolute operations ratio with
number time per second test0

0 "quicksort double pointer" 1.22 sec 13.15 M 1.00
1 "quicksort double pointer_class" 1.34 sec 11.92 M 1.10
2 "quicksort DoubleValueWrapper pointer" 1.51 sec 10.58 M 1.24
3 "quicksort DoubleValueWrapper pointer_class" 1.61 sec 9.96 M 1.32
4 "quicksort DoubleValueWrapper10 pointer" 1.51 sec 10.58 M 1.24
5 "quicksort DoubleValueWrapper10 pointer_class" 1.61 sec 9.96 M 1.32
</pre>

Again, we have some slowdowns when increasing abstraction, but not as much as we saw in the insertion sort.
That is partly due to the different complexities of the algorithms being tested: Insertion sort is O(N^2) and Quicksort is O(NLogN). Also, the 3 sort algorithms in this test file use pointers, values, indexing and incrementing very differently.

<h3>Heap Sort</h3>
<pre>
test description absolute operations ratio with
number time per second test0

0 "heap_sort double pointer" 1.36 sec 11.79 M 1.00
1 "heap_sort double pointer_class" 1.42 sec 11.27 M 1.05
2 "heap_sort DoubleValueWrapper pointer" 1.37 sec 11.66 M 1.01
3 "heap_sort DoubleValueWrapper pointer_class" 1.51 sec 10.57 M 1.12
4 "heap_sort DoubleValueWrapper10 pointer" 1.39 sec 11.53 M 1.02
5 "heap_sort DoubleValueWrapper10 pointer_class" 1.72 sec 9.32 M 1.26
</pre>

And we still have slowdowns with increasing abstraction.

<h4>Conclusions for MSVC 2008:</h4>
<ul>
<li><b>MSVC 2008</b> could improve code generation related to C++ abstraction.</li>
</ul>

<hr>
<h2>MSVC 2005 Comparison</h2>

<h3>Accumulate MSVC2005</h3>
<pre>
test description absolute operations ratio with
number time per second test0

0 "double pointer" 4.55 sec 878.16 M 1.00
1 "double pointer_class" 4.55 sec 878.16 M 1.00
2 "DoubleValueWrapper pointer" 4.54 sec 881.06 M 1.00
3 "DoubleValueWrapper pointer_class" 4.55 sec 878.16 M 1.00
4 "DoubleValueWrapper10 pointer" 4.55 sec 878.16 M 1.00
5 "DoubleValueWrapper10 pointer_class" 4.54 sec 881.06 M 1.00
</pre>

Good - very similar times, and no problems with increased abstraction.

<h3>Insertion Sort MSVC2005</h3>
<pre>
test description absolute operations ratio with
number time per second test0

0 "insertion_sort double pointer" 1.19 sec 1.69 M 1.00
1 "insertion_sort double pointer_class" 1.17 sec 1.71 M 0.99
2 "insertion_sort DoubleValueWrapper pointer" 1.19 sec 1.69 M 1.00
3 "insertion_sort DoubleValueWrapper pointer_class" 1.19 sec 1.69 M 1.00
4 "insertion_sort DoubleValueWrapper10 pointer" 1.19 sec 1.69 M 1.00
5 "insertion_sort DoubleValueWrapper10 pointer_class" 1.19 sec 1.69 M 1.00
</pre>

<b>MSVC 2008</b> produces faster code in one case, but significantly slower code in 2 cases.
And <b>MSVC 2005</b> doesn't have any penalty for increased abstraction -- all the times are close to the same.

<h3>Quicksort MSVC2005</h3>
<pre>
test description absolute operations ratio with
number time per second test0

0 "quicksort double pointer" 1.22 sec 13.16 M 1.00
1 "quicksort double pointer_class" 1.23 sec 12.98 M 1.01
2 "quicksort DoubleValueWrapper pointer" 1.54 sec 10.36 M 1.27
3 "quicksort DoubleValueWrapper pointer_class" 1.54 sec 10.36 M 1.27
4 "quicksort DoubleValueWrapper10 pointer" 1.56 sec 10.26 M 1.28
5 "quicksort DoubleValueWrapper10 pointer_class" 1.54 sec 10.36 M 1.27
</pre>

This is close to the same as <b>MSVC 2008</b>, but faster in each case involving the pointer class.
There is still some penalty for using the value abstractions.

<h3>Heap Sort MSVC2005</h3>
<pre>
test description absolute operations ratio with
number time per second test0

0 "heap_sort double pointer" 1.36 sec 11.79 M 1.00
1 "heap_sort double pointer_class" 1.37 sec 11.65 M 1.01
2 "heap_sort DoubleValueWrapper pointer" 1.37 sec 11.65 M 1.01
3 "heap_sort DoubleValueWrapper pointer_class" 1.37 sec 11.65 M 1.01
4 "heap_sort DoubleValueWrapper10 pointer" 1.40 sec 11.40 M 1.03
5 "heap_sort DoubleValueWrapper10 pointer_class" 1.37 sec 11.66 M 1.01
</pre>

This is much better than <b>MSVC 2008</b>, faster on 3 tests, and showing little penalty for increased abstraction.

<h4>Conclusions for MSVC 2008 compared with MSVC 2005:</h4>
<ul>
<li><b>MSVC 2008</b> produced faster code then <b>MSVC 2005</b> in one test.</li>
<li><b>MSVC 2008</b> produced slower code than <b>MSVC 2005</b> in 8 tests.</li>
<li><b>MSVC 2008</b> has increased abstraction penalties in the insertion sort and heap sort tests.</li>
<li><b>MSVC 2008</b> seems to have the most problems in code involving pointer_class.</li>
</ul>

Performance/Analysis/Example2

2008-06-30T00:24:36Z

Summary:

<h2>Loop Invariant Code Motion and LLVM</h2>

Now let's take a look at the results from simple_types_loop_invariant.cpp<P>

We'll use <b>LLVM-gcc</b> 2.1, specifically:
<pre>
gcc version 4.0.1 (Apple Computer, Inc. build 5449)(LLVM build 2.1)
Apple PowerMac G5 2.5 Ghz Quad Processor
</pre>

<pre>llvm-g++ -I. -O3 simple_types_loop_invariant.cpp -o simple_types_loop_invariant_llvm
./simple_types_loop_invariant_llvm > simple_types_loop_invariant_llvm.txt</pre>

<hr>
<h2>Integer math</h2>
The int32_t case is fairly representative of all the integer results under <b>LLVM</b>.

<pre>
test description absolute operations ratio with
number time per second test0

0 "int32_t variable add" 2.57 sec 622.57 M 1.00
1 "int32_t multiple variable adds" 2.57 sec 622.57 M 1.00
2 "int32_t variable subtract" 2.57 sec 622.57 M 1.00
3 "int32_t multiple variable subtracts" 3.52 sec 454.55 M 1.37
4 "int32_t variable multiply" 3.84 sec 416.67 M 1.49
5 "int32_t multiple variable multiplies" 3.86 sec 414.51 M 1.50
6 "int32_t variable divide" 24.36 sec 65.68 M 9.48
7 "int32_t multiple variable divides" 53.19 sec 30.08 M 20.70
8 "int32_t multiple variable mixed" 3.86 sec 414.51 M 1.50
9 "int32_t variable and" 1.95 sec 820.51 M 0.76
10 "int32_t multiple variable and" 1.99 sec 804.02 M 0.77
11 "int32_t variable or" 2.56 sec 625.00 M 1.00
12 "int32_t multiple variable or" 2.58 sec 620.16 M 1.00
13 "int32_t variable xor" 1.99 sec 804.02 M 0.77
14 "int32_t multiple variable xor" 1.96 sec 816.33 M 0.76
</pre>

<h3>addition</h3>
This is good. Multiple loop invariant adds are the same speed as a single add.
And that means the compiler moved the loop invariant calculations out of the loop.

<h3>subtraction</h3>
Hmm, multiple loop invariant subtracts take longer than a single subtract.
That means that <b>LLVM</b> failed to optimize loop invariant subtraction.
And that is really surprising because it did optimize addition.

<pre>
for (x=0;x<count;++x)
result += input[x] - v1 - v2 - v3 - v4;
</pre>

should have been optimized to
<pre>
temp = v1 + v2 + v3 + v4;
for (x=0;x<count;++x)
result += input[x] - temp;
</pre>

An assembly dump shows that <b>LLVM</b> issues each subtract inside the loop.

<h3>multiplication</h3>
Also good. This runs a little slower than adds due to instruction latency, but is optimized correctly.

<h3>division</h3>
Clearly not optimized. Hmm, what was the source for this?

<pre>
for (x=0;x<count;++x)
result += ((((input[x] / v1) / v2) / v3) / v4);
</pre>

Whoops! That can't be optimized for integer math without getting wrong results.
I messed up and used the wrong test code, and failed to catch it for months.
I'll have to change the test to include something that can be moved out of the loop.

<h3>mixed math</h3>
This should be the same speed as a single add, but isn't. And yet it is not as slow as if all the operations were done in the inner loop.

<pre>
for (x=0;x<count;++x)
result += input[x] + v1 - v2 * v3 / v4;
</pre>

should have been optimized to
<pre>
temp = v1 - v2 * v3 / v4;
for (x=0;x<count;++x)
result += input[x] + temp;
</pre>

Reading the assembly shows that <b>LLVM</b> did move the multiply and divide out of the loop, but kept 2 adds and a subtract.
This is probably related to whatever caused the subtract case to fail earlier.

<h3>bitwise and</h3>
Good.

<h3>bitwise or</h3>
Both versions run about the same speed, but how is this running slower than a <b>bitwise and</b>?
Reading the assembly shows that <b>LLVM</b> did optimize the multiple <b>bitwise or</b>s correctly,
generating almost identical code to the <b>bitwise and</b> loops.
But there's an interesting problem - the 7 instruction <b>bitwise or</b> loops straddle a cacheline boundary.
On some CPUs (like the PowerPC 970 aka G5) that can add significant stalls.
If I change the code slightly (by removing some other tests), the loops fall on better alignment and run as fast as the <b>bitwise and</b>.

<h3>bitwise xor</h3>
Good.
<br>

<h3>Other sizes and unsigned values</h3>
The 8, 16, 64 bit and unsigned values are very similar to int32_t but are also hitting unaligned
loop problems that make analysis of optimizations a little more difficult (without reading all the assembly).

<h3>Conclusions for integer loop invariants</h3>
<ul>
<li>With the -O3 flag for optimization, <b>LLVM</b> is usually moving integer loop invariant calculations out of inner loops.</li>
<li><b>LLVM</b> does not optimize loop invariant integer subtracts. <i>[ LLVM 2.3 fixes this problem - ccox ]</i></li>
<li><b>LLVM</b> is not aligning loops and can have code position dependent slowdowns on some processors. <i>[ LLVM team is working on it - ccox ]</i></li>
</ul>

<hr>
<h2>Floating point math</h2>

<pre>
test description absolute operations ratio with
number time per second test0

0 "float variable add" 3.84 sec 416.67 M 1.00
1 "float multiple variable adds" 6.20 sec 258.06 M 1.61
2 "float variable subtract" 3.85 sec 415.58 M 1.00
3 "float multiple variable subtracts" 6.20 sec 258.06 M 1.61
4 "float variable multiply" 3.84 sec 416.67 M 1.00
5 "float multiple variable multiplies" 4.72 sec 338.98 M 1.23
6 "float variable divide" 18.57 sec 86.16 M 4.84
7 "float multiple variable divides" 53.81 sec 29.73 M 14.01
8 "float multiple variable mixed" 3.85 sec 415.58 M 1.00

test description absolute operations ratio with
number time per second test0

0 "double variable add" 3.84 sec 416.67 M 1.00
1 "double multiple variable adds" 6.23 sec 256.82 M 1.62
2 "double variable subtract" 3.84 sec 416.67 M 1.00
3 "double multiple variable subtracts" 6.22 sec 257.23 M 1.62
4 "double variable multiply" 3.84 sec 416.67 M 1.00
5 "double multiple variable multiplies" 4.17 sec 383.69 M 1.09
6 "double variable divide" 18.58 sec 86.11 M 4.84
7 "double multiple variable divides" 53.80 sec 29.74 M 14.01
8 "double multiple variable mixed" 3.85 sec 415.58 M 1.00
</pre>

<b>LLVM</b> fails to completely optimize even a single case.
But the assembly dump shows that it does partly optimize the mixed math case similar to the way it did for integers.

<h3>Conclusions for floating point loop invariants</h3>
<ul>
<li>With the -O3 flag for optimization, <b>LLVM</b> is rarely moving floating point loop invariant calculations out of inner loops.</li>
<li>NOTE: LLVM doesn't do the FP optimizations because the LLVM architect believes it would affect the result of the FP operations.</li>
</ul>

Performance/Analysis/Example1

2008-05-30T03:23:29Z

Summary:

<h2>Loop Unrolling and GCC</h2>

Let's take a look at the output from loop_unroll.cpp, compiled with <b>gcc</b> 4.0.1.
(not to pick on <b>gcc</b>, but it gives some very interesting results)

And to be specific:
<pre>
Apple PowerMac G5 2.5 Ghz Quad Processor
gcc version 4.0.1 (Apple Computer, Inc. build 5367)
</pre>

<pre>g++ -I. -O3 loop_unroll.cpp -o loop_unroll_gcc
./loop_unroll_gcc > "loop_unroll gccO3.txt"</pre>

<hr>
<h3>Integer loop unrolling</h3>
I'm only copying the first 10 results of each section to save space.

<pre>
test description absolute operations ratio with
number time per second test0

0 "int32_t for loop unroll 1" 12.10 sec 198.35 M 1.00
1 "int32_t for loop unroll 2" 13.94 sec 172.17 M 1.15
2 "int32_t for loop unroll 3" 10.61 sec 226.20 M 0.88
3 "int32_t for loop unroll 4" 8.91 sec 269.36 M 0.74
4 "int32_t for loop unroll 5" 9.62 sec 249.48 M 0.80
5 "int32_t for loop unroll 6" 9.77 sec 245.65 M 0.81
6 "int32_t for loop unroll 7" 9.16 sec 262.01 M 0.76
7 "int32_t for loop unroll 8" 9.86 sec 243.41 M 0.81
8 "int32_t for loop unroll 9" 9.31 sec 257.79 M 0.77
9 "int32_t for loop unroll 10" 8.96 sec 267.86 M 0.74</pre>

The times are more or less decreasing with the unroll factor, and the minimum time is reached after an unroll factor of 4 or more.
This is close to the pattern we expect to see when loops are unrolled by hand and the compiler doesn't do any further unrolling.
In fact, with only -O3, <b>gcc</b> does not unroll loops (missing out on an important optimization!).
So later, we'll have to try another test with <b>gcc</b>'s -funroll-loops flag.

Because unrolling by a factor of 2 got slower than a non-unrolled loop, we can also guess that <b>gcc</b>
has some trouble scheduling the instructions (it should have been the same or faster).
A look at the assembly code confirms that the factor of 2 case has a few more stalls than the non-unrolled case.
I am a little worried that the times go back up when unrolling by a factor of 5 or more.
But another look at the assembly shows that it's just more less-than-optimal scheduling.

Alright, on to the <b>while</b> loops. These look about the same as the <b>for</b> loops.
<pre>
test description absolute operations ratio with
number time per second test0

0 "int32_t while loop unroll 1" 12.11 sec 198.18 M 1.00
1 "int32_t while loop unroll 2" 13.93 sec 172.29 M 1.15
2 "int32_t while loop unroll 3" 10.60 sec 226.42 M 0.88
3 "int32_t while loop unroll 4" 8.90 sec 269.66 M 0.73
4 "int32_t while loop unroll 5" 9.61 sec 249.74 M 0.79
5 "int32_t while loop unroll 6" 9.78 sec 245.40 M 0.81
6 "int32_t while loop unroll 7" 9.19 sec 261.15 M 0.76
7 "int32_t while loop unroll 8" 9.86 sec 243.41 M 0.81
8 "int32_t while loop unroll 9" 9.32 sec 257.51 M 0.77
9 "int32_t while loop unroll 10" 8.95 sec 268.16 M 0.74</pre>

The <b>do</b> loops are just a little different.
<pre>
test description absolute operations ratio with
number time per second test0

0 "int32_t do loop unroll 1" 11.22 sec 213.90 M 1.00
1 "int32_t do loop unroll 2" 13.46 sec 178.31 M 1.20
2 "int32_t do loop unroll 3" 10.00 sec 240.00 M 0.89
3 "int32_t do loop unroll 4" 8.89 sec 269.97 M 0.79
4 "int32_t do loop unroll 5" 9.24 sec 259.74 M 0.82
5 "int32_t do loop unroll 6" 9.78 sec 245.40 M 0.87
6 "int32_t do loop unroll 7" 8.55 sec 280.70 M 0.76
7 "int32_t do loop unroll 8" 9.74 sec 246.41 M 0.87
8 "int32_t do loop unroll 9" 9.30 sec 258.06 M 0.83
9 "int32_t do loop unroll 10" 8.67 sec 276.82 M 0.77</pre>

<b>do</b> loops are faster <b>for</b> the non-unrolled case than <b>for</b> or <b>while</b> loops.
That means that <b>gcc</b> may have some problems normalizing the different loop forms or with
instantiating the templates. Unfortunately, reading the assembly and compiler intermediate data
didn't help me identify the exact cause.
But it is still close to the results for the <b>for</b> loops after unrolling by a factor of 2 or more.

Finally, the <b>goto</b> loops look similar to the <b>do</b> loops.
<pre>
test description absolute operations ratio with
number time per second test0

0 "int32_t goto loop unroll 1" 11.21 sec 214.09 M 1.00
1 "int32_t goto loop unroll 2" 13.46 sec 178.31 M 1.20
2 "int32_t goto loop unroll 3" 10.18 sec 235.76 M 0.91
3 "int32_t goto loop unroll 4" 8.90 sec 269.66 M 0.79
4 "int32_t goto loop unroll 5" 9.24 sec 259.74 M 0.82
5 "int32_t goto loop unroll 6" 9.77 sec 245.65 M 0.87
6 "int32_t goto loop unroll 7" 8.56 sec 280.37 M 0.76
7 "int32_t goto loop unroll 8" 9.74 sec 246.41 M 0.87
8 "int32_t goto loop unroll 9" 9.30 sec 258.06 M 0.83
9 "int32_t goto loop unroll 10" 8.66 sec 277.14 M 0.77</pre>

<h4>Conclusions for int32_t loop unrolling under <b>gcc</b>:</h4>
<ul>
<li>With the -O3 flag for optimization, <b>gcc</b> is not unrolling loops.</li>
<li><b>gcc</b> can generate faster code for many of these loops if it unrolled them.</li>
<li><b>gcc</b> can generate faster code for the non-unrolled <b>for</b> and <b>while</b> loops if
it generated code similar to the <b>do</b> and <b>goto</b> loops.</li>
<li><b>gcc</b> has some instruction scheduling problems on my CPU.</li>
</ul>

<hr>
<h3>Double loop unrolling</h3>

Now let's take a look at the double precision loop unrolling results.

<pre>test description absolute operations ratio with
number time per second test0

0 "double for loop unroll 1" 3.13 sec 191.69 M 1.00
1 "double for loop unroll 2" 2.23 sec 269.06 M 0.71
2 "double for loop unroll 3" 3.91 sec 153.45 M 1.25
3 "double for loop unroll 4" 7.46 sec 80.43 M 2.38
4 "double for loop unroll 5" 6.90 sec 86.96 M 2.20
5 "double for loop unroll 6" 5.79 sec 103.63 M 1.85
6 "double for loop unroll 7" 6.30 sec 95.24 M 2.01
7 "double for loop unroll 8" 6.65 sec 90.23 M 2.12
8 "double for loop unroll 9" 7.07 sec 84.87 M 2.26
9 "double for loop unroll 10" 7.30 sec 82.19 M 2.33</pre>

The times go down, then up, way up, down a little, up again, and... What the heck?
If a compiler doesn't unroll the loops beyond what the template did,
the times should decrease with larger unrolling factors.
And we know that with -O3, <b>gcc</b> is not unrolling the loops.

The <b>while</b> loops look about the same as the <b>for</b> loops.
The <b>do</b> and <b>goto</b> loops are again a little faster for the non-unrolled case.
But all of the double loops show the same unexpected timings.

What is going on?

I tried to isolate a few of the double tests so I could look at the assembly, but when I ran it I got:
<pre>
test description absolute operations ratio with
number time per second test0

0 "double for loop unroll 1" 3.13 sec 191.69 M 1.00
1 "double for loop unroll 2" 2.23 sec 269.06 M 0.71
2 "double for loop unroll 3" 1.99 sec 301.51 M 0.64
3 "double for loop unroll 4" 1.95 sec 307.69 M 0.62
4 "double for loop unroll 5" 1.92 sec 312.50 M 0.61
5 "double for loop unroll 6" 1.82 sec 329.67 M 0.58
6 "double for loop unroll 7" 1.95 sec 307.69 M 0.62
7 "double for loop unroll 8" 2.01 sec 298.51 M 0.64
8 "double for loop unroll 9" 2.06 sec 291.26 M 0.66
9 "double for loop unroll 10" 2.02 sec 297.03 M 0.65</pre>

Wait! That's not the same!

When I add back some of the other tests (<b>while</b>, <b>do</b>, <b>goto</b>, or the integer tests)
the times get worse - but not in any predictable pattern that I could see.
Somehow, <b>gcc</b> is having problems with these loops because of the surrounding code.

Sadly, the results are very similar if I compile with -funroll-loops.

<h4>Conclusions for double loop unrolling under <b>gcc</b>:</h4>
<ul><li>I can't draw any conclusions about unrolling loops with double precision math using this code,
until some bugs are fixed in <b>gcc</b>.</li>
<li><i>[I confirmed with hand unrolled code that the double loops show the same timing
patterns as the integer loops. The <b>gcc</b> bug seems related to template instantiation -- ccox]</i></li>
</ul>

<hr>
<h3>Integer loops with -funroll-loops</h3>

Now let's see what happens when we explicitly tell <b>gcc</b> to unroll the loops.
Of course, adding the extra flag is not allowed by the benchmark rules, but it is interesting to
know what would happen if <b>gcc</b> did turn on loop unrolling.

<pre>g++ -I. -O3 -funroll-loops loop_unroll.cpp -o loop_unroll_gcc_unrolled
./loop_unroll_gcc_unrolled > "loop_unroll gccO3unroll.txt"</pre>

<pre>
test description absolute operations ratio with
number time per second test0

0 "int32_t for loop unroll 1" 10.30 sec 233.01 M 1.00
1 "int32_t for loop unroll 2" 10.57 sec 227.06 M 1.03
2 "int32_t for loop unroll 3" 10.62 sec 225.99 M 1.03
3 "int32_t for loop unroll 4" 8.90 sec 269.66 M 0.86
4 "int32_t for loop unroll 5" 9.62 sec 249.48 M 0.93
5 "int32_t for loop unroll 6" 9.78 sec 245.40 M 0.95
6 "int32_t for loop unroll 7" 9.22 sec 260.30 M 0.90
7 "int32_t for loop unroll 8" 9.86 sec 243.41 M 0.96
8 "int32_t for loop unroll 9" 9.32 sec 257.51 M 0.90
9 "int32_t for loop unroll 10" 8.95 sec 268.16 M 0.87</pre>

The non-unrolled case, and the unrolled by 2 cases have improved a little.
The rest of the cases look about the same as without -funroll-loops.
It looks like <b>gcc</b> is unrolling small loops, but not larger loops.
And <b>gcc</b> is not unrolling them enough to get optimal performance, or has trouble scheduling
the instructions. A look at the assembly shows that <b>gcc</b> unrolled the non-unrolled case by a
factor of 4 (good!), but scheduled the instructions rather poorly.
The unroll factor 2 case was unrolled by an additional factor of 2, and scheduled poorly.
Ok, so <b>gcc</b> is trying to unroll the loops and just not scheduling the instructions very well after unrolling.

The <b>while</b> loops look very similar to the <b>for</b> loop results.
<pre>
test description absolute operations ratio with
number time per second test0

0 "int32_t while loop unroll 1" 10.27 sec 233.69 M 1.00
1 "int32_t while loop unroll 2" 10.58 sec 226.84 M 1.03
2 "int32_t while loop unroll 3" 10.61 sec 226.20 M 1.03
3 "int32_t while loop unroll 4" 8.90 sec 269.66 M 0.87
4 "int32_t while loop unroll 5" 9.62 sec 249.48 M 0.94
5 "int32_t while loop unroll 6" 9.78 sec 245.40 M 0.95
6 "int32_t while loop unroll 7" 9.23 sec 260.02 M 0.90
7 "int32_t while loop unroll 8" 9.87 sec 243.16 M 0.96
8 "int32_t while loop unroll 9" 9.31 sec 257.79 M 0.91
9 "int32_t while loop unroll 10" 8.97 sec 267.56 M 0.87</pre>

The <b>do</b> loops show the same oddity on the non-unrolled case as the integer loops.
<pre>
test description absolute operations ratio with
number time per second test0

0 "int32_t do loop unroll 1" 8.42 sec 285.04 M 1.00
1 "int32_t do loop unroll 2" 10.70 sec 224.30 M 1.27
2 "int32_t do loop unroll 3" 10.09 sec 237.86 M 1.20
3 "int32_t do loop unroll 4" 9.86 sec 243.41 M 1.17
4 "int32_t do loop unroll 5" 9.23 sec 260.02 M 1.10
5 "int32_t do loop unroll 6" 9.78 sec 245.40 M 1.16
6 "int32_t do loop unroll 7" 8.57 sec 280.05 M 1.02
7 "int32_t do loop unroll 8" 9.75 sec 246.15 M 1.16
8 "int32_t do loop unroll 9" 9.31 sec 257.79 M 1.11
9 "int32_t do loop unroll 10" 8.68 sec 276.50 M 1.03</pre>

And the <b>goto</b> loops look about the same as the <b>do</b> loops.
<pre>
test description absolute operations ratio with
number time per second test0

0 "int32_t goto loop unroll 1" 8.42 sec 285.04 M 1.00
1 "int32_t goto loop unroll 2" 10.69 sec 224.51 M 1.27
2 "int32_t goto loop unroll 3" 10.16 sec 236.22 M 1.21
3 "int32_t goto loop unroll 4" 9.84 sec 243.90 M 1.17
4 "int32_t goto loop unroll 5" 9.24 sec 259.74 M 1.10
5 "int32_t goto loop unroll 6" 9.77 sec 245.65 M 1.16
6 "int32_t goto loop unroll 7" 8.56 sec 280.37 M 1.02
7 "int32_t goto loop unroll 8" 9.73 sec 246.66 M 1.16
8 "int32_t goto loop unroll 9" 9.29 sec 258.34 M 1.10
9 "int32_t goto loop unroll 10" 8.67 sec 276.82 M 1.03</pre>

<h4>Conclusions for int32_t loop unrolling, with -funroll-loop:</h4>
<ul><li>With the -funroll-loops flag, <b>gcc</b> is unrolling some smaller loops.</li>
<li><b>gcc</b> can generate faster code for these loops if it did a better job of scheduling
the instructions after unrolling.</li>
<li><b>gcc</b> can still generate faster code for the non-unrolled <b>for</b> and <b>while</b>
loops if it generated code similar to the <b>do</b> and <b>goto</b> loops.</li>
</ul>

Performance/Analysis/Examples

2008-05-30T03:17:20Z

Summary:

<h2>What do all those numbers mean?</h2>

Ok, you've downloaded the benchmark source, compiled and run it, and now you have a text file with a lot of numbers.
How do you interpret those numbers?

You are looking at the raw numbers from each test, not a weighted average or formatted summary.
Eventually, we will have a web site where you can look at the raw numbers from different compilers and platforms,
as well as analysis that has broken down the raw numbers into something a little smaller and easier to digest.
But that's going to take time to build (both the analysis and the web site).
For now, these are engineering numbers, not marketing numbers. You can think of it as a list of
times taken by each of the runners in a track event, not the short list of olympic medal winners -- useful if you
want to do some analysis, but not as useful if all you want to know is the winner.

<h2>Examples of analyzing benchmark results:</h2>

[[Performance/Analysis/Example1|loop_unroll.cpp with gcc]]

[[Performance/Analysis/Example2|simple_types_loop_invariant.cpp with LLVM]]

[[Performance/Analysis/Example3|stepanov_abstraction.cpp with MSVC]]

Performance/WhatToTest

2008-05-06T00:50:43Z

Summary: /* More Complex Stuff */

What things need to be tested as part of this benchmark suite?

If you have additions or suggestions, please add them.

__TOC__

== Fundamental Concepts ==
Most of these can't easily be tested.
* regular types
* basic math
* basic flow control
* dereference
** a pointer/iterator is a regular type that can be dereferenced
* type conversion
** performance of type conversions (known to be a problem on certain compilers)

== Language Concepts ==
* abstraction
**what happens to performance when I put { } around a value?

* inheritance
**what happens if my function is in a child class, virtual, or both?
**what happens if my values are in a child class?

* function calls - how expensive are different styles of function call?
** inline, function pointer, defined in another module, etc.

* exceptions - what is the cost of using exceptions?
** throwing versus not
** compared to error return codes
** exceptions enabled or not in the compiler
** compared to setjmp/longjmp?

* RTTI - what are the costs?
** compared to per-object ids or strings

* function objects - what are the costs/benefits compared to inline functions and function pointers?

* template instantiation
** are there any problems with duplicate template bodies and code size?
** are there any problems with recursive templates or deep usage of templates?

* constructors
** Are empty constructors correctly optimized away?
** Are copy constructors correctly optimized away?
** Are default copy constructors efficient?

== Simple Idioms ==
These are building blocks, with more than one way to express them. These are commonly reused things, usually found in headers like "inlines.h", "math_utils.h", etc.

For all of these: What is the optimal implementation, and does the compiler recognize other implementations and substitute the optimal one?

* swapping 2 values
** does anything need to be tested for swapping 2 different types, or is that handled by assignment/conversion testing?
* absolute value
* min/max of 2 values
* switch versus if/else trees
* pin values to range (max, min combo)
* rotate bits within a byte/word
* byte order reversal
* round up/down
* round float to int
* thresholding
* pointer alignment tests and comparisons
* fixed point math
* extended precision math (ie: 64 bit math on a 32 bit CPU)

== Complex Idioms ==
These may require multiple optimizations to perform well, or some pattern/idiom recognition in the compiler.
These are simple algorithms important to many different tasks/fields, but are frequently the inner loops and most performance sensitive code.
<BR>

* safe bool cast from a smart pointer
* hand coded memcpy, memmove, memset, memcmp
** simple types and user defined types
** arrays and containers
* convolution
** 1D, 2D, and more?
* matrix multiplication
** 2D is common
** higher dimensions get a bit esoteric
* min/max of a sequence
* summation of a sequence
* product of a sequence
* dot product of sequences
* sorting a sequence
** many possible algorithms and implementations
** given the permutations, is this testable?
** maybe just test STL implementations?
* reversing a sequence
* rotating members of a sequence
* find/search sequence
** again, many possible algorithms and implementations
** given the permutations, is this testable?
** maybe just test STL implementations?
* lookup tables
* interleave/deinterleave buffers
* transpose block
* rotate a 2D block
** plus or minus 90 degrees
** 180 degrees
** horizontal flip
** vertical flip
** transpose
* histogram building
* stack like operations
* bitarrays and manipulations of them
* complex type and template

== Runtime and Library Support ==
These are library functions or header defined functions/macros supplied by the compiler or OS. These can sometimes be the performance limiting factor in a variety of applications.

* allocation / deletion
** new, delete
** malloc, free
** performance for various sizes (testing suballocation)

* mathlib
** all functions
** compared to inline versions of some functions

* string manipulation routines
** strcpy, strcmp, strchr, strcat, etc.
** strncpy, strncmp, strncat, etc.

* memory routines
** memcpy, memmove, memset, memcmp, etc.

* ctype routines
** isdigit, isalpha, etc.

* stdio
** printf, getc, fread, fwrite, etc.

* C++ iostreams
** cout, ostream, etc.
** compare cout versus printf

* stdlib
** strtod, strtof

* threads
** creation, destruction, sleep overhead, semaphores, mutexes

== More Complex Stuff ==
* STL containers
** insertion
*** push_front
*** push_back
*** in-order, reverse-order and random insert for ordered containers
** removal
** deletion of container
** iterating items
** reverse iterating items
** copy containers
** erase all entries
** search/find/lookup
*** in-order, reverse-order and random
** vector
*** is iteration of vector the same as iterating a pointer
*** is operator[] the same speed as indexing a pointer
*** what is the penalty for using operator at() range checking

* STL algorithms
* iostreams

* strstr / text searching
** no "best" algorithm
** large variance in optimum based on alphabet (roman text, gene sequencing, bit pattern)

* Discrete Wavelet/Fourier/Cosine/Sine Transform
** 1D (Audio, PDE spectral methods)
** 2D (video, image compression)
** simple and optimized algorithms
** wavelet and FFT have many near optimal implementations
** JPEG, MPEG

== Optimizations ==
We need to test as many optimizations as possible. Priority should be given to those that are used most often and offer the highest benefit to the most code (which isn't always easy to judge).

* algebraic simplification
* constant folding
* constant propagation
* copy propagation
* common subexpression elimination
* loop invariant code motion
* dead code elimination
* strength reduction
* value range propagation (aka Predicate Simplification?)
* loop fusion
* loop interchange
* loop normalization
* loop removal
* loop unrolling
* loop unswitching
* normalization of references
* scalar replacement of arrays
* scalar replacement of structs
* instruction scheduling
* removal of unused objects/allocations
** this may not be legal in some circumstances
* inlining
** keyword inline
** auto inline of small functions
** functions defined in classes
** functions defined in templates
** depth of inlining (could be difficult to test)
** leaf first or trunk first?
** what factors might disable inlining on some compilers?

== Conformance to Specification ==
* user specified swap in STL algorithms
* short circuit evaluation of boolean expressions
* growth policies and complexities of STL containers
* concept checks compile away to nothing

== Binary Size ==
* Are duplicate templates correctly collapsed?
* Are unused template member functions correctly removed?
* Are unused (or duplicate) static, const, and static const values correctly removed?

== Language Extensions ==
* [http://www.boost.org/ Boost]
* [http://openmp.org/wp/ OpenMP]

== Other ? ==
* ineffiency returning or working with std::pair ?

Performance/ReleaseNotes

2008-05-05T21:26:33Z

Summary:

<h1>Release 2 - December 8, 2008</h1>

<h2>Known Problems</h2>
<ul>

<li>Line out of place in functionobjects.cpp near line 334.<br>
<i><b>Moved the line to the correct location.</b></i>
</li>

<li>makefile.nt was not updated to include the new test files<br>
<i><b>Fixed makefile.nt, posted update.</b></i>
</li>

</ul>
<br>

<h2>Files</h2>

<dl>

<dt>functionobjects.cpp</dt>
<dd>
This is a demonstration of the performance of of function pointers, functors, and native comparison operators. Some compilers have difficulty instantiating simple functors.
</dd>
<dt>simple_types_constant_folding.cpp</dt>
<dd>
A test to see if the compiler will correctly fold constants and simple constant math for simple types. Results may be surprising.
</dd>
<dt>stepanov_vector.cpp</dt>
<dd>
Similar to the abstraction penalty benchmark, this file tests what happens when we move from pointers to vector iterators and when we use reverse iterators. This tests the compiler supplied STL implementation in addition to the compiler itself. Some good compilers are crippled by bad STL implementations.
</dd>

</dl>

<h1>Release 1 - May 5, 2008</h1>

<h2>Fixed Problems</h2>
<ul>
<li>Some Linux distributions have incomplete MACH/gcc headers. I need a simple way to determine whether they have the TR1 headers or not. Unfortunately, I don't have any of those distributions.
<i><b>Related code is now commented out.</b></i>
</li>

<li>Some 64 bit Linux distributions don't like benchmark_stdint.hpp.
<i><b>Fix is posted, but really needs to be tested on more OSes.</b></i>
</li>

<li>At least one embedded compiler didn't like the order of templates in loop_unroll.cpp.
<i><b>Changed the template order.</b></i>
</li>

</ul>
<br>

<h2>Files</h2>

<dl>

<dt>loop_unroll.cpp</dt>
<dd>
Test to see if compilers will correctly unroll loops to hide instruction latency. Some compilers have problems expanding the templates, and most compilers have problems correctly unrolling the loops for best performance.
</dd>
<dt>simple_types_loop_invariant.cpp</dt>
<dd>
A test to see if the compiler will move loop invariant calculations out of the loop. Most compilers have room for improvement.
</dd>
<dt>stepanov_abstraction.cpp</dt>
<dd>
An expanded version of the original test, answering "what happens to performance when I wrap a value in curly braces?" Almost all compilers do well on the original summation tests, but they don't do nearly so well on simple sort routines using the same abstractions.
</dd>

<dt>machine.cpp</dt>
<dd>
A utility program to print out information about the compiler version, OS, and machine environment - because it is nice to know which build of your compiler generated a particular report, and which of the 30 machines in your lab that it was run on.
</dd>

<dt>benchmark_algorithms.h</dt>
<dd>
Templated algorithms shared by several test files.
</dd>
<dt>benchmark_results.h</dt>
<dd>
Shared result reporting and formatting functions for all tests, must work in C and C++.
</dd>
<dt>benchmark_shared_tests.h</dt>
<dd>
Templated test functions shared by several test files.
</dd>
<dt>benchmark_stdint.h</dt>
<dd>
Standard type definitions, required because some compilers still have not picked up C99 standard headers.
</dd>
<dt>benchmark_timer.h</dt>
<dd>
Shared timer function for all tests, must work in C and C++.
</dd>

<dt>makefile</dt>
<dd>
Make information for Unix based OSes. "make report" to build all binaries and start a benchmark run.
</dd>
<dt>makefile.nt</dt>
<dd>
Make information for Windows. "nmake -f makefile.nt report" (in a shell/command prompt with the appropriate compiler variables set) to build all binaries and start a benchmark run.
</dd>

<dt>LICENSE_1_0_0.txt</dt>
<dd>
License details, a copy can also be found at http://stlab.adobe.com/licenses.html .
</dd>
<dt>README.txt</dt>
<dd>
Basic information about the benchmark suite: goals, rules, and instructions on how to build and run.
</dd>

</dl>

How To Write A Simple Lexical Analyzer or Parser

2008-05-02T02:33:51Z

Summary: /* A Simple Recursive Decent Parser */

== Introduction ==

This ''paper'' is a response to an e-mail question asking if anyone had code to validate that a sequence of characters was a valid XML name which was not a reserved XML name (starting with <tt>'x'|'X' 'm'|'M' 'l'|'L'</tt>) or a qualified name (one containing <tt>':'</tt>). ''See [http://www.w3.org/TR/REC-xml/#sec-common-syn Section 2.3 of the XML Specification].''

Languages are defined using a grammar. There are many notations for grammars but most use some variant of [http://en.wikipedia.org/wiki/Extended_Backus–Naur_form Extended Backus-Naur form] (EBNF), XML is no exception to this rule. The variant of EBNF used for the XML notation is described in [http://www.w3.org/TR/REC-xml/#sec-notation Section 6 of the XML Specification]. Transforming an EBNF grammar into a lexical analyzer and/or parser is a relatively straight forward process. For simplicity I define the lexical analyzer as the system which transforms a stream of characters into tokens and the parser as the system which transforms a stream of tokens into a sequence of actions for each production rule. There are libraries, such as the [http://www.boost.org/doc/libs/1_35_0/libs/spirit/index.html Boost Spirit Library] and tools such as [http://en.wikipedia.org/wiki/Lex_programming_tool Lex] and [http://en.wikipedia.org/wiki/Yacc Yacc] which can be used to aid in writing lexical analyzers and parser. Knowing how to write these systems simply and directly is an invaluable tool in any programmers tool chest and experience with writing such systems will make you more productive when using libraries and tools and give you some insight into when you should and should not use them. Some issues (including this one) can also be addressed by writing a regular expression using a library such as the [http://www.boost.org/doc/libs/1_35_0/libs/regex/doc/html/index.html Boost Regex Library] - however, dealing with the numerous ranges of values in the grammar production with this problem are difficult to express in a regular expression. A [http://en.wikipedia.org/wiki/Finite_state_machine finite automata] can also be constructed for many such problems (including this one) and such systems have the advantage of inverting control flow - you put values into a finite automata as opposed to executing a parse function which pulls values from a stream.

When you look at a typical EBNF grammar it will frequently not distinguish which parts are the lexical analyzer production rules and which are the parser production rules - the structure of both a simple parser and simple lexer will be the same. The separation is the point where the value returned by the production rule is not a character from the stream, but some form of token. Because the structure is the same I'm going to refer from here on to both parts as simply the ''parser''.

== A Simple Recursive Decent Parser ==

To solve the problem of validating an XML name we're going to write a simple recursive decent, or top-down, parser. The idea is to read from a stream of characters denoted by a pair of InputIterators - we will only need to read each character once without backtracking. A grammar which can be read in this form without backtracking is known as an [http://en.wikipedia.org/wiki/LL_parser LL(1)] grammar.

To do this we are going to translate each production rule into a function which will return a <tt>bool</tt> with the value <tt>true</tt> if it recognizes the production and false if it does not. If it does recognize the production then the stream will be advanced to the end of the production and a value will be updated with the recognized production. Otherwise, the stream and value are left unchanged. Such a function will follow this pattern:

<pre>
bool is_production(I& first, I last, T& value);
</pre>

The stream denoted by <tt>[first, last)</tt> is going to be UTF16 code points because that is how the XML specification is defined. We'll define code_point_t to be a 16 bit integer:

<pre>
typedef uint16_t code_point_t;
</pre>

Rather than passing <tt>first</tt> and <tt>last</tt> through all of our functions we're going to create a simple struct which holds them and write the <tt>is_production()</tt> as a member function:

<pre>
template <typename I> // I models InputIterator
// require value_type(I) == code_point_t
bool is_production(T& value);

I f_m; // first
I l_m; // last
};
</pre>

Writing the body of the production is simple. We start at the top level production rule and work our way down - in this case we are interested in parsing <tt>Name</tt>. The <tt>Name</tt> production rule looks like this:

<pre>
Name ::= (Letter | '_' | ':') (NameChar)*
</pre>

And we could write this production something like the following:

<pre>
bool is_name(string16_t& s)
{
string16_t result;
code_point_t c;

/* (Letter | '_' | ':') */
if (is_letter(c) || is_match('_', c) || is_match(':', c)) ; else return false;

result += c;

/* (NameChar)* */
while(is_name_char(c)) result += c;

s = result;
return c;
}
</pre>

Here string16_t is our token type. For this problem, we don't actually care what the token value is - and constructing the token is relatively expensive. If we were writing a full-blown XML parser we would spend some energy on dealing with tokens efficiently. This code also doesn't tell is if the name is qualified or reserved - those are attributes of our token value. We rewrite the function to drop the token and add some attributes. We'll deal with attributes in a similar fashion to the value of the production rule, except if the production rule is recognized the attributes will be accumulated (as opposed to overwritten). We don't need to pass the attribute to all production rules, only those that have attributes. Here is the definition of our attribute type:

<pre>
enum xml_parse_attribute_t {
xml_none = 0,
xml_qualified = 1,
xml_reserved = 2
};

xml_parse_attribute_t& operator|=(xml_parse_attribute_t& r, xml_parse_attribute_t x)
{ r = xml_parse_attribute_t(r | x); return r; }
</pre>

We define <tt>operator|=()</tt> on our type to make it simple to accumulate. <tt>xml_qualified</tt> will mean that the name contains a <tt>':'</tt> and <tt>xml_reserved</tt> will mean it starts with the sequence <tt>xml</tt>. To check if the name is reserved we unroll the first couple of iterations of our loop:

<pre>
bool is_name(xml_parse_attribute_t& a)
{
code_point_t c;

if (is_match(':', c)) { a |= xml_qualified; }
else if (is_letter(c) || is_match('_', c)) ; else return false;
bool reserved = c == code_point_t('X') || c == code_point_t('x');

if (is_name_char(c, a)) ; else return true;
reserved &= (c == code_point_t('M') || c == code_point_t('m'));

if (is_name_char(c, a)) ; else return true;
reserved &= (c == code_point_t('L') || c == code_point_t('l'));

while (is_name_char(c, a)) ;

if (reserved) a |= xml_reserved;

return true;
}
</pre>

Now we can write our remaining production rules. We'll tackle <tt>NameChar</tt> next. This is the only other production rule which needs to deal with attributes because it may contain a <tt>':'</tt>.

<pre>
NameChar ::= Letter | Digit | '.' | '-' | '_' | ':' | CombiningChar | Extender
</pre>

The specification of the XML parser is in terms of UCS2 code points (as opposed to characters) and this production is only going to recognize a single code point. Except for the minor complexity introduced to handle the attribute, the code is nearly identical to the production rule.

<pre>
bool is_name_char(code_point_t& c, xml_parse_attribute_t& a)
{
if (is_match(':', c)) { a |= xml_qualified; return true; }

return is_letter(c) || is_digit(c) || is_match('.', c)
|| is_match('-', c) || is_match('_', c) || is_combining_char(c) || is_extender(c);
}
</pre>

The <tt>is_letter()</tt> function is even simpler:

<pre>
Letter ::= BaseChar | Ideographic
</pre>
<pre>
bool is_letter(code_point_t& c) { return is_base_char(c) || is_ideographic(c); }
</pre>

The <tt>is_match()</tt> is a helper function for ''terminal'' productions. A terminal production is a production which is not defined in terms of another production. It is in the terminal productions where the interesting work is done. Here is the body.

<pre>
bool is_match(code_point_t x, code_point_t& c)
{
if (f_m == l_m || *f_m != x) return false;
c = x; ++f_m; return true;
}
</pre>

If we are at the end of our steam or the current character is not a match then return <tt>false</tt>. Otherwise we set our value to the matched character, increment the stream, and return <tt>true</tt>.

The remaining productions are all of a form which match one of a set of code points:

<pre>
Ideographic ::= [#x4E00-#x9FA5] | #x3007 | [#x3021-#x3029]
</pre>

Some of the tables, such as the one for <tt>BaseChar</tt> are quite large making it prohibitively expensive to write an expression like <tt>(0x4E00U <= x && x <= 0x9FA5U) || (x == 0x3007U) || ...</tt>. Instead we will create a simple lookup table. When dealing with a parser that works with a simple <tt>char</tt> type we could just build a table with 256 elements that contained an enumeration indicating what production rule the character matched. A table of 16 bit values would be a bit large (but we could do it - 64K elements) - but instead we'll create an array of values denoting ranges which contain the code points we want to match and search to find if our character is in one of the ranges. To do that we'll create a semi-open ranges for each character range of the form <tt>(f0, l0], (f1, l1], ...</tt> and then use <tt>lower_bound()</tt> to search the table, if we end up on an odd index (starting at 0) then the item is in the range, an even index it is not. This strategy means we can't represent a range which includes <tt>0</tt> but <tt>0</tt> is not a valid character in an XML production. The code for the table lookup for <tt>Ideographic</tt> is this:

<pre>
bool in_ideographic(code_point_t c)
{
static const code_point_t table[] =
{
0x4DFFU, 0x9FA5U, // [#x4E00-#x9FA5]
0x3006U, 0x3007U, // #x3007
0x3020U, 0x3029U // [#x3021-#x3029]
};

return (adobe::lower_bound(table, c) - boost::begin(table)) & 0x01;
}
</pre>

To transform from the closed ranges to the semi-open ranges we subtract one from the first item in the range. This code doesn't have to be a member function and is not a template - we can put these lookup tables in a .cpp file. We'll use this function in our <tt>is_ideographic()</tt> member function:

<pre>
bool is_ideographic(code_point_t& c) { return is_match(in_ideographic, c); }
</pre>

<tt>is_match()</tt> is another variant of our previous is_match which takes a predicate function instead of a value:

<pre>
bool is_match(bool (*p)(code_point_t), code_point_t& c)
{
if (f_m == l_m || !p(*f_m)) return false;
c = *f_m; ++f_m; return true;
}
</pre>

The remaining productions are written the same way - just with larger tables. Our parser is complete!

Finally - to make this a little simpler to invoke we write a wrapper function which just creates a temporary instance of the class and we add one last check to make sure that the valid name made up the entire range provided:

<pre>
template <typename I> // I models InputIterator
// require value_type(I) == code_point_t
bool valid_name_unqualified_unreserved(I f, I l)
{
xml_parser<I> parser = { f, l };
xml_parse_attribute_t a = xml_none;
return parser.is_name(a) && parser.f_m == l && a == xml_none;
}
</pre>

That's the complete code. Besides having a solution to our problem we have a general framework for building other solutions to parsing problems and a pretty decent start that can be reused for other XML related issues. Parsers written in this style are simple to extend even if they are packaged as a library, you can simply inherit from the struct and add additional productions. The code described here took very little time to write (the biggest hassle was building the larger lookup tables from the productions in the XML specification.

The complete example file can be found [http://stlab.adobe.com:8080/@md=d&cd=//sandbox/papers/xml_parser_example/&cdf=//sandbox/papers/xml_parser_example/xml_parser_example.cpp&c=9XT@//sandbox/papers/xml_parser_example/xml_parser_example.cpp?ac=64&rev1=2 here.]

Compositing Models

2008-04-21T20:46:57Z

Summary:

A common point of confusion with the property model library (aka Adam) is that this is a mechanism for constructing user interfaces. That isn't the case. The property model library is a library for constructing models of how discrete properties interact. These properties might represent the parameters to a function (as is often the case in a dialog) or may be properties of the document itself.

Viewing the property model library as being part of the UI, leads one to attempt to construct a composite of layered models. Unfortunately, this doesn't work.

The key to the Model-View-Controller pattern is that it is, logically, a simple DAG:

<center>
[[image:composite_model_00.png]]

''Model-View-Controller''
</center>

Using the property model library to build the model has many advantages including:

* The property model is able to handle bidirectional relationships and solve based on a priority mechanism.
* The same model can be driven from a script or API with no UI attached.
* The model tracks contributing values which are useful for generating intelligent script which capture the user ''intent''.
* The model tracks connected components (components which may contribute) and this information is useful to control the enable/disable state of widgets (a disconnected component cannot contribute so the controller is disabled).

The property model library does have some limitations including:

* Only handles discrete values, no mechanism for modeling sequences or other structures.
* Only handles many-to-one relationships, no support for many-to-many relationships.

There are times where the property model library is not the correct answer - before determining that the property model library is not the correct solution for you problem it is very important that you understand what you are modeling. There are many cases where people dismiss the property model library because they think it is somehow ''only'' a UI mechanism. Also, it is frequently the case the clients believe that they are dealing with a document model, when in fact they are dealing with a model of function parameters (sometimes ''function'' is called ''command''). Distinguishing the two cases is important. A simple test is to ask if any constraints in the model are in fact invariants on the model or, rather, constraints imposed as a mechanism to construct parameters to a function that will operate on the model.

Treating a property model as part of the UI will lead to attempts to composite the property model with some other model. It is very tempting to bind the UI to a sheet and then have a model treat the view interface on the sheet as a way to connect another model (treating the sheet as a controller) and connect back to the sheet through the controller interface (treating the sheet as a view). This leads to the following structure:

<center>
[[image:composite_model_01.png]]

''Poorly Composited Models''
</center>

Here "Model A" is the property model and "Model B" is some other model. The figure-eight links between the two create a problem. For example - let's say a request to change the model comes in from the controller to ''A''. The view is notified of the change before ''B'' gets a crack at the data - this is akin to an electrical short.

<center>
[[image:composite_model_02.png]]

''Effect of Controller Request''
</center>

The once ''B'' gets the data, runs it through it's model and then attempts to notify the changes back, then we find that ''B'' will be notified of the change it just made.

<center>
[[image:composite_model_03.png]]

''Effect of View Update''
</center>

This is the same problem we have with any widget library which has logical state. I'm frequently heard telling people that if their widget has a ''get'' function then it is incorrect. The simplest solution to this problem is simply not to use ''A'' at all, provide your own model and don't use the property model library. Another solution, of course, is to only use the property model library. Because of the convenience of binding a layout to the property model library, however, some people still insist on attempting to composite models in this form (one side effect is an assert that fires in sheet_t::update() when it is re-entered. It may appear that the system would work without this assert, however, the first thing update() does is clears a set dirty flags - re-entering update() will give undefined behavior as to which views will be notified of the change that was in progress.

There is a supported way that models can be composited - the property model library allows any function to be plugged in to calculate a derived value, such a function can be arbitrarily complex and work on arbitrary data types. This can be used to effectively embed another model within the property model library:

<center>
[[image:composite_model_04.png]]

''Using Functions to Embed Models''
</center>

This structure allows you to keep all of the advantages of the property model library.

A number of clients would like to use the property model library simply as a [http://en.wikipedia.org/wiki/Breadboard breadboard]. This would effectively remove the property model from the system except as a connection point:

<center>
[[image:composite_model_05.png]]

''Breadboard Model''
</center>

There is currently no way to do this with the property model library. It would not be difficult to add - likely I would add a new cell type, ''connection'', and an input/output API which would let you connect to the two halves of the cell. Input will always refer to information coming from the controller, output information going to the view. So a widget would set the input cell and another model would monitor the input cell, and set the output cell which a view would monitor. This would really just be a conduit and not have much at all to do with the property model library (these cells could not be referenced from the sheet) but would provide a breadboard to connect other models to.

Performance/home

2008-03-17T23:49:23Z

Summary:

Not much here yet. This will hold a lot of the documentation for the C++ Benchmarks suite.<P>
See http://stlab.adobe.com/performance/ for the suite main web site.

* [[Performance/ReleaseNotes|Release notes]]

* [[Performance/Analysis/Examples|Some example analyses of results]]

* [[Performance/WhatToTest|What is tested and what needs to be tested?]]