I had a party for a friend visiting from Chicago last week. Drank way too much of course. Not bad for a school night, although I planned ahead and took the day off. Then I caught a bad cold or a mild flu off a house-mate, and got stuck with that over the whole bloody weekend.
Over that same weekend I worked on an introduction to Cell B.E. programming. Quite a lot. A series of worked examples starting from a plain C Mandelbrot generator, through various phases of SPUification and SIMDisation up to a final high performance(?) implementation. And all the trials and tribulations, discoveries and tricks along the way. I'm looking to publish a chapter a week or so to a new free software Cell hacking site that will hopefully come together soon. I wrote it using texiweb, using literate programming. Eight postable chapters plus introduction and appendices so far, and there are still plenty of ideas to explore.
And to top it off, yesterday I was cooking some meat on the BBQ, and I wanted to check the flame setting -- which tends to involve looking under the front. I didn't notice the folding chair right where my head was heading to, so I got a rather heavy bump on my forehead that seems to hurt more now than it did at the time.
After the party and flu I finally went to work today but I think I could've done with another day off. Apart from not being fully past the virus, it feels as though I'm suffering withdrawal from all the hyper-active hacking I've been doing on the couch over the last few days. Empty heart, irritable disposition, and feelings of exhaustion and despair.
Tuesday, 31 March 2009
Tuesday, 24 March 2009
Layout via Optimisation
Since I mentioned linear programming in the last entry I've managed to wrap my head around it enough to come up with a possible solution for my layout issues.
Now a recursive layout algorithm has trouble with this. It can't determine the offset of B without knowing the size of A, but the size of A depends on the offset of B. You need to do at least a couple of size and layout passes, and even then I'm having trouble getting it working (and I don't have the perserverance to keep trying).
It seems at first that solving the simultaneous equations would work. But in general this isn't useful because there is nothing to stop negative widths being created -- which isn't terribly useful. And determining enough additional terms to constrain the solution (e.g. that D left = A left) requires calculation itself.
Changing this to an optimisation problem allows it to be defined without the need for it to be fully specified. And constraints keep the values pointing the right way.
After a bit of fiddling about, I think I've come up with a basic systematic procedure which should allow the determination of the results using the simplex algorithm. It may not be the most optimal setup, but it appears to be relatively robust so far.
Applied to the problem above, first, trivially define the object function in terms of the left and right bounds of every box:
p = ar + al + bl + br + cl + cr + dl + dr
This is a minimisation problem in p.
Next define the widths:
br - bl = 40
dr - dl = 100
ar - al >= 0
cr - cl >= 0 (since we know this is B width / 2, we could just use 20 too)
Define the container relationship -- everything inside A must be inside A:
br - ar <= 0 cr - ar <= 0 dr - ar <= 0 al - cl <= 0 al - bl <= 0 al - dl <= 0 Everything is relative to A, so set A's left edge to 0, so it doesn't float up to meet the highest other boundary. al = 0 Now define the layout relationships. B centre = A centre bl + (br - bl)/2 = (ar - al) / 2 or bl/2 + br/2 - ar/2 + al/2 = 0 C width = B width / 2 cr - cl = (br - bl)/2 or br/2 - bl/2 - cr + cl = 0 C left = B right + 5 cl = br + 5 or cl - br = 5 D right = B right dr = br dr - br = 0 And running the simplex method over this system generates everything I need directly: Optimal Solution: p = 650; ar = 160, al = 0, bl = 60, br = 100, cl = 105, cr = 125, dl = 0, dr = 100 (calculated using http://www.zweigmedia.com/RealWorld/simplex.html) Nice. And just as a test, lets shrink D to be smaller than B, say 30.
Optimal Solution: p = 440; ar = 90, al = 0, bl = 25, br = 65, cl = 70, cr = 90, dl = 35, dr = 65
Still works.
It should be able to calculate both dimensions and deeper structures simultaneously. This will allow relationships across dimensions, e.g. A width = B height * factor + offset.
One thing the recursive layout routine handled ok was affine transforms (after a lot of mucking about mind you). I guess this should handle them too if I get the coordinate space correct. Relative position calculations need to be in parent space, but the layout calculations need to be in global space.
Now I just have to work out how to calculate those parameters from expression trees, and find out if a solver will run fast enough. Actually I'm pretty confident of the performance question, even a trivial implementation I wrote for work did thousands of rows and columns in a few hundred ms.
Example layout problem:
If I just consider the horizontal coordinates, the following known values and relationships describe this layout:
B centre = A centre
B width = 40
C width = B width / 2
C left = B right + 5
D width = 100
D right = B right
Want to know:
Left and right of every box.
Now a recursive layout algorithm has trouble with this. It can't determine the offset of B without knowing the size of A, but the size of A depends on the offset of B. You need to do at least a couple of size and layout passes, and even then I'm having trouble getting it working (and I don't have the perserverance to keep trying).
It seems at first that solving the simultaneous equations would work. But in general this isn't useful because there is nothing to stop negative widths being created -- which isn't terribly useful. And determining enough additional terms to constrain the solution (e.g. that D left = A left) requires calculation itself.
Changing this to an optimisation problem allows it to be defined without the need for it to be fully specified. And constraints keep the values pointing the right way.
After a bit of fiddling about, I think I've come up with a basic systematic procedure which should allow the determination of the results using the simplex algorithm. It may not be the most optimal setup, but it appears to be relatively robust so far.
- Trivially define the objective function in terms of the sum of every left and right X coordinate.
- Define width relationships - the known knowns, or the known unknowns.
- Define container constraints - every child is fully inside its parent. Unless the parent size is defined explicitly, in which case do not add any implicit relationship.
- Define layout constraints.
Applied to the problem above, first, trivially define the object function in terms of the left and right bounds of every box:
p = ar + al + bl + br + cl + cr + dl + dr
This is a minimisation problem in p.
Next define the widths:
br - bl = 40
dr - dl = 100
ar - al >= 0
cr - cl >= 0 (since we know this is B width / 2, we could just use 20 too)
Define the container relationship -- everything inside A must be inside A:
br - ar <= 0 cr - ar <= 0 dr - ar <= 0 al - cl <= 0 al - bl <= 0 al - dl <= 0 Everything is relative to A, so set A's left edge to 0, so it doesn't float up to meet the highest other boundary. al = 0 Now define the layout relationships. B centre = A centre bl + (br - bl)/2 = (ar - al) / 2 or bl/2 + br/2 - ar/2 + al/2 = 0 C width = B width / 2 cr - cl = (br - bl)/2 or br/2 - bl/2 - cr + cl = 0 C left = B right + 5 cl = br + 5 or cl - br = 5 D right = B right dr = br dr - br = 0 And running the simplex method over this system generates everything I need directly: Optimal Solution: p = 650; ar = 160, al = 0, bl = 60, br = 100, cl = 105, cr = 125, dl = 0, dr = 100 (calculated using http://www.zweigmedia.com/RealWorld/simplex.html) Nice. And just as a test, lets shrink D to be smaller than B, say 30.
Optimal Solution: p = 440; ar = 90, al = 0, bl = 25, br = 65, cl = 70, cr = 90, dl = 35, dr = 65
Still works.
It should be able to calculate both dimensions and deeper structures simultaneously. This will allow relationships across dimensions, e.g. A width = B height * factor + offset.
One thing the recursive layout routine handled ok was affine transforms (after a lot of mucking about mind you). I guess this should handle them too if I get the coordinate space correct. Relative position calculations need to be in parent space, but the layout calculations need to be in global space.
Now I just have to work out how to calculate those parameters from expression trees, and find out if a solver will run fast enough. Actually I'm pretty confident of the performance question, even a trivial implementation I wrote for work did thousands of rows and columns in a few hundred ms.
Monday, 23 March 2009
Z**D
Well I've been hacking on, of all things, a 2D structured diagram drawing application.
It came out of a lack of satisfaction with pretty well any GUI application I've tried. They look good on paper but when you try to do things with them you find all sorts of nasty limitations. One of the biggest problems they have is creating lots of objects of the same kind with different settings (think, uml classes). On the other hand, there are purely text or language based formats, which are good for editing lots of items quickly, and you can control layout very well, but they have steep learning curves, and making small tweaks to attain visual perfection is very time consuming. I haven't had the chance to use many CLI applications -- perhaps GNUPlot is the closest. They provide graphical output but no chance for graphical input. Like GNUPlot, many are focused on scientific users too.
So I want to experiment with a combined CLI, GUI, and ``active source'' user interface. I guess it might end up being a bit ambitious, but it'll give me something to keep me off the streets for a while.
Some of the ideas so far:
I've done some work on the language parser, and the language itself is an interesting problem, and there's plenty of room to experiment. Do I go for minimalistic syntax, and put more of the semantics into the execution of the AST, or do I wrap up more of the language in reserved words? Do I use special symbols (e.g. ~ for a curve, "foo" for a label), or stick to English keywords (curve x ..., label "blah" ...)? GUI-modifications-to-source operations --- essentially graphical refactoring tools --- will probably be quite some work too.
And I have some layout code that mostly works. Although I've already hit some issues with containers which must automatically size to their contents. Because of the arithmetic and relationship based layout system there is the potential for complex relationships that are difficult, expensive, or impossible to calculate using recursive layout procedures and delayed arithmetic. Maybe linear programming will come to the rescue, if I can get my head around it - should be able to just calculate all the layout at once. But ... It will need some symbolic expression refactoring, which doesn't sound too fun.
It came out of a lack of satisfaction with pretty well any GUI application I've tried. They look good on paper but when you try to do things with them you find all sorts of nasty limitations. One of the biggest problems they have is creating lots of objects of the same kind with different settings (think, uml classes). On the other hand, there are purely text or language based formats, which are good for editing lots of items quickly, and you can control layout very well, but they have steep learning curves, and making small tweaks to attain visual perfection is very time consuming. I haven't had the chance to use many CLI applications -- perhaps GNUPlot is the closest. They provide graphical output but no chance for graphical input. Like GNUPlot, many are focused on scientific users too.
So I want to experiment with a combined CLI, GUI, and ``active source'' user interface. I guess it might end up being a bit ambitious, but it'll give me something to keep me off the streets for a while.
(not the real intended structure, but a quick diagram I whipped up to test some code)
Some of the ideas so far:
- CLI, GUI, and programming language are all fully first-class interactive data input options.
- CLI is an old-school CAD-like interface, where data can be input numerically.
- A ``live'' text editor where edits are reflected in the display at or near real-time.
- A typical pick'n'place GUI as well, at least for creating objects and adjusting layout.
- Item references in CLI or Editor or GUI are highlighted in the alternative input views.
- Declarative language allows flexibility, yet still allows direct GUI relationships.
- Language more human oriented than parser oriented.
- Custom graphical objects defined in declarative language, including object-like features.
- Custom graphical objects also defined in Java classes.
- Flexible layout mechanisms based on anchor points and vector arithmetic. Somehow available from GUI too.
- Heirarchical objects and grouping.
- Cascading styles using same syntax as language.
I've done some work on the language parser, and the language itself is an interesting problem, and there's plenty of room to experiment. Do I go for minimalistic syntax, and put more of the semantics into the execution of the AST, or do I wrap up more of the language in reserved words? Do I use special symbols (e.g. ~ for a curve, "foo" for a label), or stick to English keywords (curve x ..., label "blah" ...)? GUI-modifications-to-source operations --- essentially graphical refactoring tools --- will probably be quite some work too.
And I have some layout code that mostly works. Although I've already hit some issues with containers which must automatically size to their contents. Because of the arithmetic and relationship based layout system there is the potential for complex relationships that are difficult, expensive, or impossible to calculate using recursive layout procedures and delayed arithmetic. Maybe linear programming will come to the rescue, if I can get my head around it - should be able to just calculate all the layout at once. But ... It will need some symbolic expression refactoring, which doesn't sound too fun.
Wednesday, 18 March 2009
Things afoot
I keep writing (long) posts and then decide against posting them. Social anxiety or something. How strange for an internet jot pad.
Lately I've started to get a bit busier and more serious with my hacking, so once I get something to a non-embarassing state, I might actually move forward with putting bits out there. Though, the reaching of a state of non-embarassment might mean a long wait. And i'm a little recitent about baring all to the world like that -- people might point and laugh, or even worse, start using it, leading to the descending spiral of the un-fun of on-going maintenance.
To that end I've been looking into hosting -- perhaps a bit prematurely, but it needs to be considered at some point. I had a quick look at google code, but it's license limitations rub me up the wrong way (one long-term project is server based, so AGPL is almost certainly the way i'm headed which rules it out anyway) -- it is also full of lots of rubbish, ugly, and doesn't appear to be maintained by humans. I never liked Sourceforge, it's got a sort of crappy host-of-last-resort feel to it. A mate mentioned github, but that seems a bit too light on features - mailing lists and issue trackers and so on, and I have no overt love for git, or proprietary services either.
Savannah will probably be the one -- it ticks all the boxes on features, and philosophy, and although svn has it's issues, I know how to use it. It even has some quite nice themes -- why on earth they use that god-awful super-ugly default is beyond me, but if you log on you can select some nice ones which turn it into a completely different modern-feeling site (yes I realise this thing has a shit theme too -- but this is just a single crappy `blog roll'). Their information is a little out of date on Java, to the point they suggest not using it, which I find a little odd -- but so it is in general with the FSF and GNU sites, someone needs to refresh their information. As far as I can tell (which is not far) it's all nice and happily free now. If it doesn't end up being suitable, I'll keep looking.
Apart from a couple of Java projects, a few people (well, me included) on the psubuntu list are slowly discussing setting up some sort of site for free-software Cell hacking. Since my interests have moved on a bit, and right now i'm quite busy with `other shit', I'm not sure I want to commit to such an endeavour, but I have some material which could probably help get the ball rolling.
The project i'm on at work will most probably be winding up around the end of the FY -- so I may be forced to have a LOT more spare time in a short few months. Actually i'm quite looking forward to the possibility, as the current project-winding-up phase isn't terribly exciting, and I've had more than a few gut-fulls of .NET and Windows XP to boot. Something might turn up by then, but if it doesn't, I wouldn't mind a bit of `time to myself' to re-discover some of the `knack' that went missing of late.
Right now, I just wish there were more hours in the day, and I was capable of being more alert for more of the ones that are here.
Lately I've started to get a bit busier and more serious with my hacking, so once I get something to a non-embarassing state, I might actually move forward with putting bits out there. Though, the reaching of a state of non-embarassment might mean a long wait. And i'm a little recitent about baring all to the world like that -- people might point and laugh, or even worse, start using it, leading to the descending spiral of the un-fun of on-going maintenance.
To that end I've been looking into hosting -- perhaps a bit prematurely, but it needs to be considered at some point. I had a quick look at google code, but it's license limitations rub me up the wrong way (one long-term project is server based, so AGPL is almost certainly the way i'm headed which rules it out anyway) -- it is also full of lots of rubbish, ugly, and doesn't appear to be maintained by humans. I never liked Sourceforge, it's got a sort of crappy host-of-last-resort feel to it. A mate mentioned github, but that seems a bit too light on features - mailing lists and issue trackers and so on, and I have no overt love for git, or proprietary services either.
Savannah will probably be the one -- it ticks all the boxes on features, and philosophy, and although svn has it's issues, I know how to use it. It even has some quite nice themes -- why on earth they use that god-awful super-ugly default is beyond me, but if you log on you can select some nice ones which turn it into a completely different modern-feeling site (yes I realise this thing has a shit theme too -- but this is just a single crappy `blog roll'). Their information is a little out of date on Java, to the point they suggest not using it, which I find a little odd -- but so it is in general with the FSF and GNU sites, someone needs to refresh their information. As far as I can tell (which is not far) it's all nice and happily free now. If it doesn't end up being suitable, I'll keep looking.
Apart from a couple of Java projects, a few people (well, me included) on the psubuntu list are slowly discussing setting up some sort of site for free-software Cell hacking. Since my interests have moved on a bit, and right now i'm quite busy with `other shit', I'm not sure I want to commit to such an endeavour, but I have some material which could probably help get the ball rolling.
The project i'm on at work will most probably be winding up around the end of the FY -- so I may be forced to have a LOT more spare time in a short few months. Actually i'm quite looking forward to the possibility, as the current project-winding-up phase isn't terribly exciting, and I've had more than a few gut-fulls of .NET and Windows XP to boot. Something might turn up by then, but if it doesn't, I wouldn't mind a bit of `time to myself' to re-discover some of the `knack' that went missing of late.
Right now, I just wish there were more hours in the day, and I was capable of being more alert for more of the ones that are here.
Subscribe to:
Posts (Atom)
