[This is preliminary documentation and subject to change]

Liogo and performance ?

Performance is neither the main, neither the most important feature of Liogo. Main features of Liogo are:

However nobody can think to a compiler without thinking to performance. Before Liogo 0.3, Liogo has very poor performance and the generated code was slower than any Logo interpreter. A hard work was done on Liogo 0.3 to enhance performance, more precisely on Generator, Core and Compiler. Find below some of optimization done on these modules.

Generator

As you could see in How it works, Liogo generator now use a C# constant for any literal value used in your Logo program. So, Liogo avoid multiple object creation at runtime and to spend time to allocate or garbage collect memory. Constants are used for all Logo data type: number, word and list.

In a very similar way, Logo loops are now optimized by Liogo using C# variables. So you could be sure than start value expression, end value expression and step value are all evaluated one and only one time for each loop. So for example, in the following sample each procedure is called only one time :

  
to startvalue
   output 0
end		
	
to endvalue
   output 5
end
		
to stepvalue
   output 2
end			

to dofor		
   for [i startvalue endvalue stepvalue] [ print :i ]
end

dofor

Core

The Core layer of Liogo is all classes used to represent Logo variables or values.

In Liogo 0.3, Lists are now LinkedList objects in .NET instead of ArrayList. Both types could be handled with an Add and a Remove method but ArrayList has two majors drawbacks. First, when you delete the first element of an ArrayList, a memory copy is need to shift all other items. Second, ArrayList is implemented as a growing array so each time the size grows a memory copy is need too. Due to this two points, when a list has thousands of items, list handling was terrifically slow with ArrayList. LinkedList has not these drawbacks. By the way, the memory size need for a LinkedList is more important.

Because Logo is a poorly typed language, the Liogo runtime need very often to convert values between number and word. In first versions of Liogo, these conversions were done using try/catch statements and exception handling. It was a very bad idea because exception handling have a very big overhead due to .NET stack handling needed. In Liogo 0.3, the runtime use the faster .NET method TryParse.

At runtime, a running Liogo program has two contexts:

The Liogo context is need to store variables but the call stack is just need when an exception occurs and for debugging. By the way, keeping in memory the calling stack with all parameters values has an important cost because Liogo need to do a memory copy for each value. For procedure with heavy parameter (like a list with thousands of items), it's very very costly. So, in Liogo 0.3 the full Logo call stack is just build when you compile your Logo program in debug mode, see How it works for more.

Compiler

If you read the Dynamic statements in Liogo tutorial, you know that the Logo programming language has a really dynamic nature. So, with primitives like RUN, MAP, REDUCE to name a few, you can dynamically create new statements in a Logo program. It's easy to handle for a Logo interpreter but it's hard to handle for a compiler because you need to call the compiler at run time for the new statements. Of course, calling the compiler at runtime is the worst operation in term of performance that you can ever imagine in a program.

So what if you need to iterate on a dynamic primitive in a Logo program ? Like in the following sample:

  
make "a 0
repeat 100 [run [make "a :a + 1]]
print :a

Liogo 0.3 come with a cached compiler so when you call several time the same dynamic statements, the overhead is just for the first call. This feature is specifically interesting in LIOGOI the interactive command line compiler. For example, when you type the following commands in LIOGOI:

  
LIOGOI - Logo Interpreter for .NET version 0.3.6.0
GPL Copyright (c) 2005 Lionel Laské

? forward 100
? left 90
? forward 100
? left 90
? forward 100
? left 90
? forward 100
? left 90
?

The first "forward 100" and the first "left 90" are slow because LIOGOI need to call the compiler but all other operations are very fast because commands are find in the compiler cache.

How measure performance ?

To measure performance, I choose to use the timemilli command that come with MSWLogo/FMSLogo. timemilli return a tick count so it could be used easily to do a measure between two steps of a Logo procedure. Something like this:

  
make "start timemilli
; Here is what I need to measure
make "milliseconds timemilli - :start

An advantage of timemilli is that it can also be use it with MSWLogo/FMSLogo to do a comparison.

But what performance should be measure ? Pavel Boytchev have done a great work on performance measurement for EuroLogo 2005 conference. In its article "Lhogho, The real Logo Compiler" (see here for more), he made three performance tests.

First one is Arithmetic benchmark, it's a test on multiple arithmetic computation.

  
to arithmeticbenchmark :limit
	make "start timemilli

	make "s 0
	make "n 1
	repeat :limit [
           make "s :s + 1 / :n
           make "n :n + 1
        ] 

	make "milliseconds timemilli-:start 
end

Second one is Indirect benchmark, it's a test accessing variable with expression.

  
to indirectbenchmark :limit
	make "start timemilli

	make "a 0
	make "b 0
	make "c 0
	make "v "abc
	make "n 0
	repeat :limit [
	  make "n :n + 1
	  make "w first :v
	  make "v word bf :v :w
	  make :w (thing :w) + 1 / :n
        ]

	make "milliseconds timemilli-:start 
end

Last one is List benchmark, a test with heavy list handling.

  
to listbenchmark :limit
	make "start timemilli

	make "n :limit
	make "a []
	repeat :n [
	   make "a fput :n :a
	   make "n :n-1
	]

	make "b []
	while [not empty? :a] [
	  make "b fput first :a :b
	  make "a bf :a
        ]

	make "milliseconds timemilli-:start 
end

I choose to do three more tests to measure performance on some other points.

Convert benchmark measure capacity to quickly switch between number and word value.

  
to convertbenchmark :limit
	make "start timemilli

	make "a 0
	make "b [1 A B]
	make "c 0
	make "d 0
	repeat :limit [
	  make "a :a + "1
          ifelse (item (modulo :a 3)+1 :b) = 1 [make "c :c+1] [make "d :d+1] 
	]

	make "milliseconds timemilli-:start 
end

Dynamic benchmark show overhead to call the compiler at runtime.

  
to dynamicbenchmark :limit
	make "start timemilli

	make "a 0
	make "b 0
	make "n 0
	repeat :limit [
	  run [make "n :n + 1]
          make "b map [?] (list :a)
	]

	make "milliseconds timemilli-:start 
end

Graphic benchmark is used to measure time to draw a large number of segments. This test draw fractals using Koch algorithm.

  
to koch :size :n
	if :n=0 [fd :size stop]
	koch :size/3 :n-1
	lt 60
	koch :size/3 :n-1
	rt 120
	koch :size/3 :n-1
	lt 60
	koch :size/3 :n-1
end

to graphicbenchmark :limit
	make "start timemilli

	rt 90
	pu sety 160 pd
	repeat :limit/1024 [
		koch 200 6
		pu setx 0 sety 160-repcount*40 pd
	]

	make "milliseconds timemilli-:start 
end

And the winner is...

Optimize Liogo compiler is cool but: Is Liogo is faster than a Logo interpreter ? it's what we'll see now.

To measure performance, I choose to iterate 100, 1 000, 10 000, 100 000 and 1 000 000 times each previous test. I launched each test few times and take the worst time. I launched tests on Liogo 0.3 for .NET Framework 2.0 and on FMS Logo 6.7.2. I used my Laptop: a Dell Latitude D610 with 1 Go RAM on Windows XP SP 2. Results may vary on other platforms.

Each chart below shows in dark green the Liogo result and in light green the FMS Logo result. The X-axis shows the number of loop iteration and the Y-axis is a logarithmic value of the elapsed time in milliseconds. For your information, I'll give the average performance enhancement between Liogo 0.2 and Liogo 0.3.

Arithmetic benchmark

This first chart below shows that Liogo has better results than FMS Logo on arithmetic operations but this difference decrease when the number of iteration increase. Performance enhancement between Liogo 0.2 and Liogo 0.3 is 300%.

Convert benchmark

Again Liogo has better results than FMS Logo on convert operations but after 100 000 iterations the FMS Logo performances are slightly better. Here, performance enhancement between Liogo 0.2 and Liogo 0.3 is 600% !.

Indirect benchmark

One time again Liogo is better for indirect operations when number of iteration is less than 10 000 iteration but FMS Logo is better after. Performance enhancement between Liogo 0.2 and Liogo 0.3 is 130%.

Graphic benchmark

Here, Liogo is better for every number of iteration and because Y-axis is logarithmic it means that performance is twice to fourth time better than FMS Logo. However, I must confess that Liogo has fewer drawing features than FMS Logo so this results is not fully equitable. Performance enhancement between Liogo 0.2 and Liogo 0.3 is 170%.

Dynamic benchmark

This test is the most difficult for a compiler. How a compiler can win against an interpreter on dynamic statements ? Hopefully the compiler cache of Liogo is very useful here. Many thanks to this cache, here the performance enhancement  between Liogo 0.2 and Liogo 0.3 is 23000% !.

List benchmark

I keep the worst at last. On List benchmark, except for few items, performance of Liogo are very very poor compared to FMS Logo. By the way, performance enhancement between Liogo 0.2 and Liogo 0.3 is 300%.

Conclusion

Liogo could be better than an interpreter like FMS Logo to compute complex operations. However when the program requires an important number of values (like lists with a large number of items), Liogo performance quickly decrease. This is probably due to the design of Liogo which use heavily object oriented technology. For example in Liogo, a value is always represented by a .NET Object (LogoWord, LogoNumber or LogoList) instead of a value type. So, each operation on a value or a variable usually needs a memory allocation, a constructor call and, very often,  a memory copy. The use of .NET Framework and IL code (instead of native code) probably have an overhead too. By the way, Liogo could not exist without the power of .NET Framework !

The good news is that the hard work done on performance in Liogo 0.3 is a success: each Liogo 0.3 program is three times quicker average than the same program in Liogo 0.2. More: performance enhancement is real for all benchmarks with impressive results for convert and dynamic benchmarks.

So, as a conclusion, performance of Liogo could be better: great ! it's fun to think that the work is not over. :-)

LIOGO - GPL Copyright (c) 2005-2006 Lionel Laské