Lua Workshop 2015

I presented Ravi at the Lua Workshop 2015 held at Stockholm. You see see the slides of my presentation here.

An LLVM binding for Lua

I announced the development of Ravi back in January 2015. It started as an experiment - I was not certain whether Ravi could achieve the performance levels of LuaJIT, the reigning monarch for Lua JIT compilation.

I am pleased to report that Ravi is able to match LuaJIT's performance for a few selected benchmarks. More details are available here. While this is positive news, there is still much to do to make Ravi competitive in a variety of situations.

LuaJIT offers a powerful FFI interface for interfacing with external libraries and like. This is very convenient for sure, but the approach taken is not compatible with Lua. After some thought I decided that rather than creating an FFI interface for Ravi, a more general capability would be to allow both Lua and Ravi users to write JIT code using LLVM. Work on this has just started so there is not much to show yet, but I hope to make progress fairly quickly.

LLVM is a very low level api - lower level than C. This has its pluses and minuses. On the plus side the LLVM binding will allow Lua and Ravi users to exploit the full power of LLVM. On the minus side even writing trivial functions can be quite some effort.

SimpleDBM migrated to GitHub

As Google decided to shut down the project hosting service I have been forced to find a new home for SimpleDBM. So SimpleDBM is now hosted at the following github site:

https://github.com/dibyendumajumdar/simpledbm

Memory bugs and finding them

I am working on creating a JIT compiler for Lua and Ravi. Ravi is a Lua derived language with some enhancements to help improve performance. The JIT compilation is being implemented using LLVM.

As I implement more parts of the Lua language I am able to run more of the standard Lua test suites in JIT mode. A few days ago I encountered a nasty bug - one of the test cases failed on Windows with a run-time exception that seemed to imply an invalid or misaligned stack. Now this is a particularly hard bug to find as at runtime there is a mix of code compiled by the MSVC compiler (the Lua C code) and the code generated by LLVM. The LLVM generated code has no debugging information right now as I haven't yet implemented the required metadata. So the problem is how to investigate the issue if the fault is in LLVM generated code.

Confusingly the error only occurred on Windows - but not on Linux, so I was initially led to believe that the error may be due to some issue with how LLVM was using the stack on Windows.

The problem with memory errors is that they are Heisenbugs. Any change you do to investigate the issue such as adding a debug print may help the bug to hide. So investigation is particularly hard.

My initial attempt at finding the root cause was to run the tests under Valgrind. Valgrind reported some possible memory leaks but not in my code - the reported potential leaks were in LLVM code. There were no reports of buffer overflow or memory overwrites.

I guess that if the problem is some portion of the stack being overwritten then Valgrind cannot find it as it is more a tool for analyzing issues with heap allocation.

My next stop was to use Address Sanitizer. This is a tool created by Google engineers - it works by instrumenting the code using some compiler extensions. Fortunately this capability is available in GCC 4.8.2 which is the compiler I am using on Ubuntu. Just by adding a compiler option (-fsanitize=address) one can get instrumented C code. The tool not only checks heap allocations but also the stack for invalid reads/writes.

When I ran the test suite with the instrumented version asan reported an issue and aborted the program. Fortunately, you can just run the application under GDB, and break at the point where asan reports the error. And if the code has appropriate debug information, then GDB will tell you the line of code that caused the error.

To cut a long story short - I found that the memory error was being caused because I had not modified the Lua Debug API to work with JITed code. I had incorrectly assumed that the Debug API is only used if invoked explicitly. When an error is raised in Lua, the error routine uses the Debug API to obtain information about the code running at the time. This relies upon the 'savedpc' field which is not populated in JITed code - so any calls to the Debug API that relies on this can lead to unexpected memory access. The fix I implemented was to treat JITed functions as if they are C functions.

The reason for this post is however that I found Address Sanitizer to be an amazing tool. It is a life saver for C/C++ programmers.  

Ravi - an attempt to create optional typing for Lua

I am in love with Lua as blogged previously. While it is perfect little language, there is scope for improving the performance of Lua. Obviously great work in this area has already been done by Mike Pall who created Luajit. However, there are some issues with Luajit that are hard to overcome.

• Large parts of Luajit are written in assembler - which means that it would take significant investment of time and effort to understand how it works and fix issues or make enhancements to it.
• Mike Pall is undoubtedly a genius, but he is the sole developer of Luajit. The latest version 2.1 has not been released yet as Mike is presumably working on other things as reported on his sponsorship page. So the destiny of Luajit is pretty much tied up with how much effort Mike puts into Luajit.
• Luajit was based on Lua 5.1, and for good reasons it has stayed compatible with 5.1, avoiding ABI incompatible features in later versions. But this is increasingly going to be a problem as newer versions of Lua introduce new features.
• Luajit's FFI is great but not compatible with Lua, so any code exploiting FFI is not compatible with Lua. 

So my solution to above is to enhance core Lua to support optional typing so that the VM can use type specific bytecode. This will hopefully help the interpreter performance but more importantly it will enable simple JIT compilation of performance critical functions.

I am naming this new dialect of Lua as Ravi. Full details of the project can be found at the Ravi github site.

Lua is small and small is beautiful

Lua is a tiny language and like C has a tiny standard library. Like many other users of Lua, there are times when I wish it had some language feature (ability to specify types, for example) - but when I think about who Lua is meant for by its designers, I get the logic behind keeping it really small and simple.

Although Lua is powerful enough as a language that it can be used for many complex tasks - see DynASM for an assembler written in Lua - its primary design goal is to provide applications with an extension language. So for example you have a Spreadsheet application, and you wish to allow users to write their own functions they can use in the Spreadsheet. Or you have a Editor and you wish to allow users to customise the editor. And so on. In all these use cases, we cannot assume that the end user who is coding in Lua is a competent programmer. Hence Lua needs to be ultra-simple for such users. Having types in the language, for example, would immediately complicate the syntax of Lua.

That Lua fulfils the needs of its users is evident from the fact that a number of attempts have been made to create a Lua clone that is more powerful as a language - but none of these alternative improved Lua clones have any great following (Note that I exclude LuaJIT from this list as it is 100% faithful to Lua 5.1 so it is another implementation of Lua rather than a clone). I guess the question you have to ask is:

• Are you trying to create an extension language for ordinary users who are not programmers?

If not then perhaps Lua is not the language you need. 

Lua - A fabulous programming language

Last year I discovered Lua and LuaJIT.

These are both amazing implementations of the programming language Lua.

Ok now I need to explain why I think Lua is fabulous and these implementations are amazing.

Lua is a very small, dynamic, scripting language that is extremely easy to learn, and that can be used standalone as well as an embedded scripting language. The well documented and well crafted C API for extending the language is probably one of the best features of the Lua system.

It takes less that a minute to compile and build the Lua language and its basic libraries. Since the language is written in ANSI C, you can virtually build it on any platform.

LuaJIT is a JIT implementation of Lua created by a guy called Mike Pall who is without a doubt a programming wizard. LuaJIT features an interpreter that is hand-crafted in assembler, and has an amazing FFI library that allows easy extensions in C, including creating new data types. LuaJIT comes with an assembler called DynASM that is itself written in Lua.

Neither of these implementations depend on third-party libraries or tools ... which is an amazing thing in today's world (just look at the dependency list of Julia for comparison).

I hope to use Lua extensively in the future, so much so that I decided to learn assembler in order to be able to understand LuaJIT better.

Should you ever embark on a complete rewrite?

I embarked on V2 of my project SimpleDBM about 3 years back. Finally last month I closed down the V2 branch and merged the useful stuff back into the main branch.

V2 was going to be a major refactoring of the system. That is what killed it - because any major refactoring is large amount of effort. One of the best write ups on why no one should ever do this is this article at Joel on Software.

That doesn't mean one should not refactor software - it is just that small incremental changes that are immediately merged and tested with the mainline is the better way to do it.

SimpleDBM is now licensed under Apache License 2.0

I am pleased to announce that as of v1.0.23 the license is changing to Apache License 2.0. The new release is available in Maven Central.

See my earlier post for the rationale for this change.

Life after Java

After working exclusively in Java for several years, I have been dabbling in C++ for the last year or so.  Question arises - is C++ still a viable language? If Tiobe Index is to be believed C++ has been steadily declining in popularity since about 2005 - coincidentally this was the year I decided to move from C++ to Java for my project SimpleDBM. At the time I stated my reasons for the move in my second blog post.

So what has happened in the meantime and is C++ still a viable language?

The place where I work (my day job) - I introduced Java in the realm of financial risk analytics. I led the team that converted a C++ based application to Java - and in the process we proved that the Java implementation was several times faster. The reason for this was nothing to do with the choice of the language - it was just that with Java you can focus on better algorithms and data structures, rather than fighting the language - which made all the difference in my view.

And yet it is in the realm of numerical computing where C++ is arguably the best language with the exception perhaps of Fortran (of which I have no experience sadly). The main advantages of C++ are:

• Ability to seamlessly call C++, Fortran and C libraries - a lot of high performance numerical libraries out there are written in these languages.
• Control of memory layout of data structures.
• Efficient array access via pointers - and no bounds checking.
• Templates for generating type specific code.

C++ is still an ugly language with too many features - but the recent changes in C++ 11 have made life tolerable if not completely easy. I have been looking at alternatives such as D, Go, Julia, etc. but haven't found a viable alternative yet. These other languages are either immature or have very restrictive paradigms. JVM based languages such as Scala have the same issues essentially as Java.

SimpleDBM now available in Maven Central

I am pleased to announce that I have finally managed to get SimpleDBM (v 1.0.22) uploaded to Maven Central.  This should make it much easier for people to use SimpleDBM in their projects.

I am working on fixing the build systems of the sample projects - the source repository has fixes for btreedemo and tupledemo samples.

Performance optimisations in typesystem

The new typesystem in v2 will only support following types:

• bool 
• int 
• long
• double
• utf8 string
• varbyte (raw)

The older version had types like BigInteger, BigDecimal, Date, VarChar.

The new typesystem attempts to be closer to native types, both for performance reasons and also so that ports to C like languages is easier.

Another major change is the way the row data is serialised. The older typesystem did not store the metadata associated with each column, therefore a separate data dictionary was required to deserialize the data.   The new typesystem encodes the types in the serialised format, therefore a row can be reconstructed from the serialised data without reference to a data dictionary. 

What is unchanged is the status byte per column. Previously this only stored the value type in the column, i.e., Null, PlusInfinity, MinusInfinity or Value. In the new version I am hoping to expand the use of the status byte to encode 3 things:

• value type - only Null or Value, taking 1 bit
• If int or long or double, then the number of bytes used to store the value - encoded in 3 bits
• If bool then the bool value encoded in 1 bit (overlayed with above, 2 bits unused)
• If utf-8 string or varbyte then 1 bit to encode if the data is zero length or not (overlayed with above, 2 bits unused)
• The remaining 4 bits to encode the type of the data.

One of the performance killers in the old version is the complete deserialization of data whenever a row is read into memory. This is a killer as the overhead of parsing certain types such as Strings, BigInteger, or BigDecimal is huge. The new version will try to avoid parsing the data whenever possible.

We all know these days that immutable objects are good for multi-threaded applications as they allow us to share data without synchronisation. The old typesystem relies heavily on immutable objects, which is one reason for parsing the row immediately upon deserialization. The problem with lazy parsing is that state must be maintained, and fields initialised upon first access - this makes the row itself mutable, and hence thread unsafe. The solution I am adopting for this is to create separate types. The Row type is immutable, but cannot directly access the bytestream of serialised data. A new type called RowReader is designed to mirror the access methods of Row, but do this over the bytestream. This type is not thread-safe - the caller must ensure that the type is not shared between threads in an unprotected manner. We shall also have a RowBuilder for constructing Row objects incrementally; the RowBuilder is also not thread-safe, and access to it must not be shared across threads in an unprotected manner.

Next version of SimpleDBM

After a break, I have resumed work on creating SimpleDBM V2. This version is mostly a refactoring of the existing codebase to ensure:

1. Better project structure - break up the project into smaller modules.
2. Simple IOC container for auto wiring the modules.
3. TypeSystem now integral part of the core, hence some modules can take advantage of the Row structure; in the current version, the TypeSystem is an add-on component.
4. Multi-licensed - SimpleDBM V2 will be available under Apache as well as GPL licenses.
5. Magic number and version info in the SimpleDBM files.

Rather than making enhancements at the same time as refactoring the codebase, I am going to keep changes to a small number, as I want to get the project restructure completed by Q1 2011. 

Moving the type system into the core is the biggest change in SimpleDBM. I think this will allow some modules to exploit the knowledge about rows and column types, and optimise for performance. Some things that may be possible are:

• Compression of data in pages
• Smaller redo log records for data updates

Note that the SimpleDBM V2 code is in a separate mercurial repository. Changes can be viewed at http://code.google.com/p/simpledbm/source/list?repo=v2.

Java versus Google Go - Part 2

The new Go Programming language from Google is very interesting because it attempts to bring to the world of compiled languages some of the benefits of the VM based languages, such as garbage collection and dynamic interfaces. I am considering porting one of my projects to Go, but before diving in, I would like to explore Go by writing a few small programs and comparing these with the Java versions.

Without further ado, here is a very simple program that reads a file and outputs lines to the console. First, lets look at the Java version:

package org.majumdar;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.Reader;

public class CatFile {

        public static void main(String[] args) {
                if (args.length == 0) {
                        usage();
                        return;
                }
                BufferedReader reader = null;
                try {
                        reader = new BufferedReader(new FileReader(args[0]));
                        String line;
                        while ((line = reader.readLine()) != null) {
                                System.out.println(line);
                        }
                } catch (Exception e) {
                        System.err.println("error: " + e.getMessage());
                } finally {
                        close(reader);
                }
        }

        private static void close(Reader reader) {
                if (reader == null)
                        return;
                try {
                        reader.close();
                } catch (IOException e) {
                }
        }
 
        private static void usage() {
                System.out.println("usage: CatFile ");
        }
}

Now, the same program implemented in Go:

package main

import "fmt"
import "os"
import "bufio"

func usage() {
        fmt.Printf("usage: catfile \n")
}

func main() {
        if len(os.Args) < 2 {
                usage()
                return
        }
        f, err := os.Open(os.Args[1], os.O_RDONLY, 0)
        if err != nil {
                fmt.Printf("error: %s\n", err)
                return
        }
        defer f.Close()
        r := bufio.NewReader(f);
        for {
                line, err := r.ReadString('\n');
                if err == os.EOF {
                        break
                }
                if err != nil {
                        fmt.Printf("error: %s\n", err)
                        break
                }
                fmt.Printf("%s", line);
        }
}

I am really not sure which one of the two is more readable.

The main differences in the two programs are in how errors are handled, and how resources are cleaned up.

Java offers the finally clause in a try block for cleaning up resources; the Go approach is to allow functions to be scheduled to be invoked when the enclosing function returns via the defer statement. The Go approach doesn't offer much programmer control over when the cleanup should occur. With a try block, the placement of the cleanup code is more under the programmer's control.

Error handling in Java is based upon exception management. Go doesn't have exception management yet; although some form of exception management is planned. The authors of Go seem opposed to exception handling as a mechanism for error handling; their argument is that the try-catch-finally construct makes the code convoluted and that encourages programmers to label ordinary errors as exceptions. My personal preference is for the Java approach because it forces you to handle the error condition. By convention in Java (although the language does not enforce this), error conditions are indicated via exceptions and not by return values.

I think with either approach you can write bad code that doesn't handle errors properly. In Java, you can do this by handling the exception incorrectly; in Go, if you forget to check for an error condition, the program will probably fail at runtime in an unexpected way.

My initial thoughts are that I prefer the try-catch-finally approach to the Go approach, both for error handling and for resource cleanup. Of course the Java approach isn't perfect; for example, the usefulness of checked exceptions is doubtful, and there could be better support for resource cleanup - in fact this is coming in Java 7.

The programs listed above are trivial, and the comparison is not really fair as the strengths and weaknesses of the two languages are not clear. I am hoping to compare two additional programs - a simple TCP/IP server implementation, and a Lock Scheduler implementation. I have the Java versions of these, and am hoping to write the Go versions in the next few days.

A Simple IOC Container

All of the SimpleDBM modules are designed with constructor based dependency injection in mind. But so far, these dependencies have been manually coded. I want to move away from manual setting up of dependencies and was therefore looking for a small IOC container that would serve my needs. Unfortunately, all the available dependency injection frameworks appear to be bloated and huge; PicoContainer used to be small, but now is  a 308k jar, SpringFramework with all dependencies is huge; Google Guice has an android edition that is 403k. Considering that SimpleDBM itself is about 632k in size, I don't fancy adding external libraries that cause the size to double or treble.

As my requirements are tiny (I only need support for singletons and constructor based dependency injection) I decided to roll out my own. The core of the IOC Container is implemented in just three files, consisting of less than 300 lines of code. Here are the links to these files:

• SimpleContainer.java - the IOC container
• Binding.java
• BindingBuilder.java

Of course it would be nice to reuse other libraries and not have to write my own, but on the plus side, you can't beat the home made solution when it comes to size. As I have also removed the dependency on Log4J, SimpleDBM is now totally self contained with no external dependencies other than the standard libraries that are shipped with JDK 5. I find this liberating.

Proposed license boilerplate

Given below is the boilerplate license notice that will be add to SimpleDBM source files from version 2 onwards. This is based upon the boilerplate used by Mozilla.org. Note that I decided to add LGPL to the mix as well, so that SimpleDBM V2 will be triple licensed. Hopefully that will ensure compatibility with the vast majority of Open Source licenses.

/**

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.

 *

 * Contributor(s):

 *

 * The Original Software is SimpleDBM (www.simpledbm.org).

 * The Initial Developer of the Original Software is Dibyendu Majumdar.

 *

 * Portions Copyright 2005-2010 Dibyendu Majumdar. All Rights Reserved.

 *

 * The contents of this file are subject to the terms of the

 * Apache License Version 2 (the "APL"). You may not use this

 * file except in compliance with the License. A copy of the

 * APL may be obtained from:

 * http://www.apache.org/licenses/LICENSE-2.0

 *

 * Alternatively, the contents of this file may be used under the terms of

 * either the GNU General Public License Version 2 or later (the "GPL"), or

 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),

 * in which case the provisions of the GPL or the LGPL are applicable instead

 * of those above. If you wish to allow use of your version of this file only

 * under the terms of either the GPL or the LGPL, and not to allow others to

 * use your version of this file under the terms of the APL, indicate your

 * decision by deleting the provisions above and replace them with the notice

 * and other provisions required by the GPL or the LGPL. If you do not delete

 * the provisions above, a recipient may use your version of this file under

 * the terms of any one of the APL, the GPL or the LGPL.

 *

 * Copies of GPL and LGPL may be obtained from:

 * http://www.gnu.org/licenses/license-list.html

 */

Multi-licensing

The next version of SimpleDBM will be available under the GPLv2 as now, as well as the Apache License. Dual licensing will allow people to use SimpleDBM in more flexible ways.

Network client server API released

I am pleased to finally publish 1.0.18-ALPHA release of SimpleDBM. This release has following changes:

• A network client server implementation that allows SimpleDBM to run as a standalone database server to which clients can connect remotely.
• A sample application that demonstrates the use of the network API. The sample implements a simple discussion forum; front end has been created using Google Web Toolkit.

The version 1.x codebase is now going into maintenance phase, as I am not going to add any new features to this version. I will start work on version 2.x which will allow me to refactor some of the modules as  previously blogged.

Licensing revisited

In a previous post I wrote about why I preferred GPL license for SimpleDBM. But I am no longer sure; my intention was always to ensure that SimpleDBM can be used by anyone without worrying about licensing issues, and I have no desire to put restrictions on other people's work. So if someone enhanced SimpleDBM, they should be free to do whatever they like with their enhancement, and although it would be nice if they contributed back, I don't insist on it. But this philosophy is very different to the GPL, which asserts that any enhancements should also be GPL.

I also did not fully understand the restrictions that GPL poses on linking with another library. Users of SimpleDBM should definitely not have to change their license or adopt GPL just to be able to use SimpleDBM in their applications.

I am seriously considering changing the SimpleDBM license to some other; probably Apache Version 2.

Roadmap

I have been thinking about how SimpleDBM should evolve. When I started the project my intention was to eventually add support for SQL, but now I can't see this happening in the near term. SimpleDBM is not aimed at competing with other SQL databases; SQL is nice because of the ease with which tables can be queries, joined etc., but implementing an SQL layer is quite a lot of work, which I am not able to put in right now.

Another subject that has interested me right from the beginning is multi-version concurrency. Unfortunately, I have not really found a way of implementing this which is satisfactory. The two main approaches are those taken by Oracle and PostgreSQL - which I have previously compared in a short paper. The Oracle approach is problematic because it requires page level redo/undo in the transaction system; SimpleDBM's BTree implementation uses logical undo, allowing for undo to be applied to a different page from the original. I do not like the PostgreSQL approach to MVCC either, as it does not support versioning in indexes.

Instead of adding large features such as above, I shall perhaps focus on the many smaller changes that I have been mulling over for some time now:

• Refactor the code so that the modularity of SimpleDBM can be exploited better. This involves separately packaging the API from the implementation, and allowing implementations of individual modules to be easily swapped in.
• Add statistics gathering so that useful metrics can be captured. Some work has been done in this area.
• Improve performance and scalability of the lock manager.
• Add support for sequences.
• Add support for reverse indexes.
• Add JMX monitoring capability.
• Refactor the type system - and make the type system a first class component of the core engine. This needs a bit of explanation. When I first started SimpleDBM, my strategy was that the core database engine should be typeless, and should allow a type system to be plugged in. The core engine should treat records and keys as blobs of data, and not worry about their internal structure. This strategy allowed me to develop the core engine without first having to define a type system. However, it has meant that some things are less efficient - for instance, row updates cause the entire before and after images of the row to be logged. Another area of concern is the ability to compress data within pages, which is hard to do without some knowledge of the structure of the data inside the records.
• Carry forward the work of making most types immutable, include row types. A row builder class can be provided to create rows, but once constructed the row should be immutable. 
• Carry on improving the documentation.
• Improve the test cases, and the test coverage.
• Create a single threaded version which can run on small devices.
• Add support for nested readonly transactions; these are useful for carrying out foreign key checks, should they be added in future.
• Ensure the embedded and network API are interchangeable, and that clients can swap between the two without having to change any code. At present, the network API is completely separate from the embedded API.
• Create a full blown sample application - work is ongoing to create this.
• Try to raise awareness about SimpleDBM and build a community of users and developers.