Saturday, January 14, 2006

0.0.6 Update

Hello there,

Just to let anyone interested know that SS development is alive and kicking; expect me to release 0.0.6 within about a week! Unfortunately, I did not find the time to work on a connection with arbitrary external libraries. There have been many small improvements, though, relative to 0.0.5.9. I also added two new largish programs:

-a stripped-down version of Pythonchess, thanks to Jyrki, the author! (360 lines)
-yet another sudoku solver, that would cause older versions of SS to choke badly (178 lines)

The former becomes about 9 times faster on my PC, but there are probably some simple optimizations I can do to improve this further. The latter really gave the type inferencer a hard time, so I added some simple heuristics to 'guess' types, for use as a starting point of the analysis. This greatly reduced the analysis time for many other tests.

Btw, the raytracer is 65 times faster on my PC at home (X2 4800+), instead of the 40 I measured in China :-)

Shed Skin now correctly compiles about 6000 lines of unit tests. Included in these are the following non-trivial programs:

-satisfiability solver 1
-satisfiability solver 2
-min/max othello player
-neural network simulator
-sudoku solver 1
-sudoku solver 2
-sudoku solver 3
-convex hull
-voronoi
-mandelbrot
-n-queens
-the pygmy raytracer
-tic-tac-toe on arbitrary-size boards
-linear algebra routines
-simple genetic algorithm
-conway game of life
-pythonchess speed test engine

I'm starting to become pretty confident the compiler will work well in general. The speedups are also pretty good in general, but I think it can be much improved still, by tweaking code generation and the C++ versions of the Python builtins. I could really use a hand here! :D

(update: Anyone would like to try and get SS to run using, say, vc++?)

5 comments:

Oliver said...

Wow, it looks like you're doing something almost as fun as my work. I'm compiling Haskell to .NET, which also has its fair share of pain :)

Not that my blog has shown this in recent times...

srepmub said...

'pain' desccribes the process quite accurately. maybe later on, we can visit a shrink together, and save some money?

Oliver said...

question about the absence of None, would it not be possible to, for instance, have a "Noneable" (cf. nullable in .NET) wrapper?

eg.
struct NoneType {} None;

template <typename T> class Noneable{
bool m_isNone;
T m_val;
public:
Noneable(const T & val):m_isNone(false),m_val(val){}
Noneable(const NoneType &none=None):m_isNone(true){}
bool isNone(){ return m_isNone; }
operator T&(){ return m_val; }
bool operator==(NoneType&){ return m_isNone; }
bool operator!=(NoneType&){ return !m_isNone; }
};

The ==/!= operators are unnecessary, but might make codegen easier (i haven't really looked at what your compiler does ... it fights my mac, and i keep forgetting to try it on my linux box at home).

This approach lets you do Noneable>int< nint; and then treat nint as an int automagically.

The problem is how you deal with attempts to get a T from None. eg. nint=None; nint+=4; logically exceptions would do, but the None checks would potentially be per access...

Obviously this would only really be necessary for primitive types, but it would certainly add some not insignificant overhead, so you'd certainly want to do some form of static analysis to ensure you don't use Noneable more often than necessary.

My Haskell compiler does something similar for primitives, but doesn't have the problem of there being None as a result -- it's dealing with lazy evaluation.

srepmub said...

Sorry about the bad mac support. Once SS compiled under OSX, but I don't have access to a mac anymore. What's going wrong?

Yeah I guess this Noneable approach would work.. :-) I haven't really thought about a static analysis for battling the overhead though..

Oliver said...

I did a few quick tests and it looks like
Noneabl doesn't cause to much overhead -- most of the problems are in function calls, because gcc rdfuses to move Noneable through registers.

Anyhoo, I'm not on my Mac now, but i'm getting a bizarre lazy binding error, haven't yet work out whats it's failing on.