Getting to the root of the gnuplot troubles

As I mentioned in my previous post, the gnuplot in Ubuntu does not work with Lush and that you have to build it yourself. The make-or-break difference between Ubuntu's and your own built is that Ubuntu's gnuplot links libeditline whereas your own built should link the GNU readline library. That's how far I got last time I looked at it, but I did not dig deeper to understand what gnuplot with libeditline does differently from gnuplot with libreadline.

The reason that the specific command-line library could have anything to do with the problem I am seeing with Ubuntu's gnuplot is that, unlike any other gnuplot interface I have seen, Lush's interface is bidirectional. The nice thing about it is that you can create a Gnuplot instance and use it to interact with gnuplot from within the Lush shell.

? (libload "gnuplot/gnuplot")
[gnuplot.lsh]
[gnuplot-config.lsh]
= "/home/juenglin/downloads/lush2-ref/packages/gnuplot/gnuplot.lsh"
? (defvar gp (new Gnuplot))
= gp
? (gp "show version")

G N U P L O T
Version 4.4 patchlevel 2
last modified Wed Sep 22 12:10:34 PDT 2010
System: Linux 2.6.32-26-generic

Copyright (C) 1986-1993, 1998, 2004, 2007-2010
Thomas Williams, Colin Kelley and many others

gnuplot home: http://www.gnuplot.info
faq, bugs, etc: type "help seeking-assistance"
immediate help: type "help"
plot window: hit 'h'

= ()
? (gp "show terminal")

terminal type is wxt 0

= ()

A bidirectional interface is more complicated to implement than a unidirectional interface. The nuts and bolts of a unidirectional interface consist of creating a pipe, spawning a gnuplot process and making the read end of the pipe the processe's standard input. Use the write end of the pipe to send commands and data to gnuplot and you are basically done.

What makes a bidirectional interface more complicated is not so much that one needs to use two pipes, but the difficulty of staying in sync with gnuplot without getting into a deadlock. The approach of the current implementation of Lush's bidirectional interface is to launch gnuplot in interactive mode and to use the gnuplot prompt as a cue for when to stop reading from the receiving pipe. The protocol basically mimics the interaction a user has within the gnuplot shell: enter a command, type return, see gnuplot's answer and a new gnuplot prompt.

Now, what's wrong with libeditline? It turns out that when running gnuplot with libeditline in this mode, gnuplot never sends a prompt. I haven't quite figured out why that is the case. But as an experiment I connected to gnuplot via a pseudo terminal and it turns out that gnuplot with libeditline then sends the prompt and the interface works. Unfortunately, using pseudo terminals for the interface is not a solution as the communication seems to go a lot slower than with pipes.

Using Lush with Gnuplot

I had not been using Lush for about a year and yesterday I wanted to write a few lines of code to recreate a plot from a linear algebra textbook. This is the sort of thing that people turn to Matlab for: write a few lines of code to generate some data, call plot once or twice, done. When I am on the top of my game I can do the same with Lush, it would not take me more than ten minutes.


The plot in question shows the roots of Wilkinson's polynomial in the complex plane and illustrates that polynomial root finding is an ill-conditioned problem. The thicker black dots are the known roots of the polynomial and the many little red dots are the roots returned by a polynomial root finder after perturbing the polynomial's coefficients slightly. More precisely, the program randomly perturbed the coefficients, called the root finder and plotted the roots in red. Repeating this 100 times you get a plot like the one above.

The point of the plot is that the exact location of the roots as a function of the polynomial coefficients is very sensitive for this polynomial. Perturbing the coefficients cause changes in the roots' locations many orders of magnitude larger than the changes in the coefficients.

The point of this blog post, on the other hand, is to show how easy it is to generate that plot in Lush. Here is the function that created the plot (the complete script is in Lush's demos directory).

(defun wilkinson-demo (&optional (n-pertubations 100))
  (let* ((p *p-wilkinson*)
     (n ($n *p-wilkinson*))
     (s ($> [@ 1e-10] n-pertubations n))
     (coeffs (* ($< p n-pertubations) (+ 1 (rand s))))
     (plotter (new Gnuplot 'interactive ())) )
    (plot
      (title "Roots of Wilkinson's polynomial")
      (points (++> *roots-wilkinson* [0]) (lc 'black) (pt 7) (ps 1))
      (do ((c coeffs))
        (points (poly-solve c) (lc 'red) (pt 7) (ps 0.2)) ))
    plotter))

Just a few lines, nice. But yesterday it took me more than half a day to get this done. Not because I forgot so many things about the language, but because I had not fully rebuilt everything I needed after upgrading my laptop a few months back: The gnuplot installed on Ubuntu simply did not work with Lush and I had to figure out/remember why.

Long story short, if you want to use gnuplot with Lush (you do), then you need to build it yourself. That is, download the sources, install all the development packages for the dependencies that make gnuplot most powerful and pleasant to use (libreadline, wxWidgets, cairo, pango, libgd), and build it.

I installed the most recent version 4.4. and the gnuplot demos in Lush all worked fine.

The mm_manage call

I have been away working on my thesis and on Lush 2 for the last few months. The garbage collector got quite a bit faster since and I made changes to the API. The most recent change was the introduction of the mm_manage call.

mm_manage(const void *p);

With mm_manage you hand to MM a pointer to memory that you allocated with a C library function (malloc, calloc, stdrup, etc.). MM then will take care of it and free the memory for you when it is no longer referenced.

This call makes MM more useful in situations where you get objects from calls into third-party code that uses the C library functions for memory allocation. Of course, you may use mm_manage only for memory objects that are leafs in the dependency graph that MM oversees, and mm_manage assigns those the memory type mt_blob. (The type mt_blob is a predefined, unsized memory type for things that don't contain further memory references).

What if a library does return something more complicated than a blob? For instance, the OpenCV API contains functions like cvFindContours that builds up a complicated data structure, which you need to hold on to and traverse and query with other OpenCV functions. While the address to the data structure created by cvFindContours is, to an OpenCV user, an address to something opaque and pretty much a blob conceptually, you may not simply call free with this address (and therefore you cannot give it to mm_manage).

However, for every call that builds an object, OpenCV has a counterpart, a destructor function, which releases the object. With a little bit more work the mechanism behind mm_manage may be extended to deal with such objects as well. What is needed is a variant mm_manage_foreign, which not only takes a pointer, but, in addition, a custom free function that MM will call instead of free when the object becomes unreachable:

typedef void free_func_t(void *p);
mm_manage_foreign(const void *p, free_func_t *f);

MM would tag those foreign addresses with a special memory type mt_foreign instead of mt_blob and maintain a mapping from foreign pointers to their respective free functions. And mm_manage will then be equivalent to

mm_manage_foreign(p, free);

End of SoC

It has almost been a month since my last post, and Google Summer of Code has come to an end. Although I have not achieved all my milestones, this project is nevertheless a success. The Lush interpreter is now powered by the new memory manager module and the result of my SoC work is the basis for "Lush 2", the next major Lush release (see https://lush.svn.sourceforge.net/svnroot/lush/).

The garbage collector is faster now than a few weeks ago thanks to using a bitmap to record the state of the small object heap. Not maintaining free lists at all but using the bitmap for finding unused memory in the small object heap might give further improvements, albeit small ones. I will try it out some time, after describing the work in a brief tech report.

Debugging and Tuning

Friday last week I had a major break-through: I saw the shell again after more than four weeks. Debugging was exactly as much fun as everybody says it is. It's particular frustrating if you spend five hours from not having any clue what part of the system might be causing a crash over narrowing it down to a small number of hypotheses to finding a really stupid mistake that you can't believe you are responsible for. Gdb is a close friend now.

For testing the interpreter I was basically using the startup procedure. When the interpreter starts up it reads in and parses a bunch of source files with definitions. So there surely are a couple of more bugs that this "test" did not expose. Before I try running other programs to tease out more bugs, though, I will spend a little more time on performance tuning. Having to wait a minute or two until the interpreter got to a point where it broke while parsing the standard files was an annoyance while debugging last week (and besides, that performance is unacceptable).

Three items are on my performance tuning to-do list for now:

• Do some profiling and try to speed up the hot spots in the MM code
  
• Implement asynchronous collect (so far there's only synchronous)
• Implement a smarter collection trigger policy