Floris' Blog

The other day I saw this article on resume writing at java world: What HR Professionals Look For in a Programmer’s Resume, which is a nice read. It’s a follow-up to the even better How to Make HR Dump A Programmer’s Resume.

In my part-time role as coach/mentor I come across a few CVs that would benefit from the articles.

It also reminded me of an article by Steve Yegge: http://steve-yegge.blogspot.com/2007/09/ten-tips-for-slightly-less-awful-resume.html

Today I was listening to epsiode 81 of Floss Weekly (a podcast on Open Source Software. Randal and Leo were talking with Steve Coast of OpenStreetMap.org. I’m familiar with the data of openstreetmap.org for use both in my own application for GPX editing, as well as for navigation.

When they were talking about the cycling maps, I had a look at what they currently look like, and the maps at www.opencyclemap.org have greatly improved since I last looked at them. There’s lot’s of details for the Netherlands!

I also stumbled onto another variant (not discussed during the podcast): openpistemap.org. This project maps all ski areas, with lifts and routes, as well as the difficulty level! Even though it is still summer, this makes me look forward to some snowboarding again!

This is another article I wrote for the newsletter of my employer. These articles are intended as an introduction to algorithms. This one takes a look at the shortest path algorithm. Text is in Dutch:

Het kortste pad algoritme kom je in veel puzzels tegen. In sommige puzzels is het overduidelijk dat hiernaar gevraagd word, en in andere moet je door het verhaal heen prikken om het te vinden. Over het algemeen komt het erop neer dat er gevraagd wordt om een enkele waarde terug te geven die zo klein mogelijk is, waarbij je veel invoer data krijgt waarmee je een graaf op kunt bouwen. In veel gevallen is de exacte route niet van belang (er zouden meerdere oplossingen kunnen zijn, wat het jureren ingewikkelder maakt) en is er sprake van een startpunt in de graaf.

Voor hele kleine structuren zou je de oplossing kunnen vinden door recursief door alle oplossingen te gaan: je begint in het gegeven startpunt. Voor iedere uitgaande mogelijkheid kijk je of de knoop aan de andere kant nog niet in je huidige pad zit. Als het er wel in zit ga je verder met de volgende uitgaande mogelijkheid. Anders kijk je of de knoop waar je heen gaat voldoet aan bepaalde eindcriteria (een te bezoeken punt). Als dat zo is dan bereken je de pad lengte, die sla je op, en je gaat verder met de volgende uitgaande mogelijkheid. Anders herhaal je deze stappen voor de betreffende knoop (weer alle volgende uitgaande mogelijkheden nalopen). Als je geen uitgaande paden meer hebt, dan ga je naar terug naar de knoop waar je vandaan kwam om daar de volgende optie te proberen.

Deze manier van oplossen is al snel onbruikbaar. Het aantal te proberen paden loop snel op, waarbij veel stukjes van de route meerdere keren uitgerekend worden.

De oplossing voor dit probleem is de door Edsger Dijkstra bedacht in 1959. De essentie van de oplossing is dat je bij iedere stap een knoop kiest die nog niet eerder gekozen is en die de kleinste afstand heeft vanaf de start-knoop. Een mooie visualisatie hiervan is door de knopen als voorwerpen voor te stellen die met draadjes aan elkaar zitten en op tafel liggen. Als je nu de start-knoop van tafel pakt en omhoog trekt, dan komt even later een knoop van tafel die op de kleinste afstand van de start zit. De volgende knoop die van tafel komt heeft ook een minimale afstand vanaf de start. Eventuele overbodige verbindingen zijn te herkennen als draden die slap hangen tussen twee knopen die van tafel zijn.

Het algoritme begint door voor iedere knoop een paar waardes te initialiseren: de ‘vorige knoop’ (nuttig om de optimale route terug te kunnen geven, maar vaak niet nodig) en de ‘minimale afstand’ die we op oneindig initialiseren, behalve voor de startknoop: die krijgt 0 als afstand. Verder maken we een set waarin alle knopen zitten.

Zolang de set niet leeg is voeren we de volgende stappen uit. Eerst zoeken we in de set naar de knoop met de laagste minimale afstand. Dit is de knoop die van tafel zou komen. Deze knoop noemen we ‘A’ en we halen deze uit de set. We gaan over alle uitgaande verbindingen van A. Voor iedere knoop aan de andere kant van die verbinding (laten we deze ‘C noemen) kijken we of de minimale afstand groter is dan de minimale afstand van A plus de afstand van de verbinding. Als dat het geval vervangen we de minimale afstand van C door de minimale afstand van A plus de afstand van de verbinding en wordt de waarde ‘vorige knoop’ van C gezet op A.

Voor verschillende problemen zijn er kleine optimalisaties te maken in het algoritme. Je kunt eerder stoppen als je de afstand naar het gevraagde punt gevonden hebt. Je kan ook de set initialiseren met alleen de startknoop en er elementen aan toe voegen als de minimale afstand wordt aangepast. Dit helpt het zoekwerk naar de knoop met de laagste minimale afstand te versnellen. Er zijn ook data structuren die het vinden van die knoop versnellen (priority queue), maar al deze optimalisaties kosten extra geheugen of boekhoud -werkzaamheden, waardoor ze niet altijd een verbetering betekenen.

Dijkstra’s algoritme is het bekendste algoritme voor het oplossen van kortste pad problemen. Er zijn er echter meer, of varianten:

Floyd-Warshall algoritme – berekent de kortste afstand van ieder punt naar ieder ander punt. Bruikbaar als in een probleem vanuit (veel) verschillende startpunten routes bepaald moeten worden. Nadeel is dat alleen al het opslaan van al die afstanden kwadratisch is met het aantal knopen (en je snel te weinig geheugen hebt).

A* algoritme – een optimalisatie voor kortste pad problemen. Je zoekt dan niet naar de knoop met de kortste afstand vanaf de startknoop maar naar de knoop met de laagste waarde voor ‘kortste afstand vanaf de startknoop’ plus een geschatte afstand tot de eindknoop. De schatting moet hierbij nooit overschatten. Dit zorgt ervoor dat de gezochte oplossing eerder gevonden wordt.

Op Spoj kun je de volgende puzzels doen om met shortest pad te spelen:
440. The Turtle´s Shortest Path - Eenvoudig, maar let op I/O
96. Shopping
3405. Almost Shortest Path

It’s time for James’ toy show! He first gave some Duke’s choice awards to Terracotta, Atlassian and blueJ. The Jagex team gave a demo of the editors used for RuneScape character creation and landscape creation: the ease with which these seem to work is amazing. Simon Ritter and Angela Caicedo did some demo’s (the card projection and virtual painting on frosted glass). Tor Norbye showed what can be done with the new JavaFX editor. Debugging a simcard on a mobile phone plus communication with a remote SunSpot failed to impress. The winners of the FIRST robotics competition got on stage and had some fun gathering objects and throwing them at James. They received an award because FIRST is switching to Java as the platform to develop on, and because it just looks cool. With someone from ND SatCom, James showed a picture from his youth, programming on a PDP-8 for satellite communications before showing how Java is now used to control the basestations and perform spectrum analysis. Visuvi was asked on stage to demo their image search engine: mindblowing. Grameen Foundation facilitates micro-finance using their ‘mifos’ platform and showed that platform to us. Check1two demonstrated their jukebox app, with their CEO playing(?) the ’starving musician’ role. Two students from Bulgaria demonstrated their winning entry in a Ricoh contest with an application that scans and rates multiple choice answer sheets. Volkswagen electronics showed their work to get an Audi TTS rallycar to drive autonomous over a track, based on JavaRTS (project Bixby). The show ended with a project announced on JavaOne last year. Last year Neal Young mentioned going for the automotive X-prize: This year the LincVolt is presented: an old Lincoln continental, converted to run on batteries (which can be charged using a generator) and Java.

‘Under the Hood: Inside a High-Performance JVM Machine’ provided looks into the JVM (seemingly that of IBM, but many concepts apply to all modern JVMs). Performance has been improved over the last years by better processors (and understanding the memory hierarchy), better language understanding (idiom recognition) and processing budget (taking advantage of new instructions and more cores). The talk went over the architecture (and the way that makes Java run on multiple platforms) and into the optimizations in the JIT. From a tree and some other data, multiple optimizations (a library of ~150 optimizations) can be iteratively applied. The choice for applying a certain optimization is based on code quality compile-time trade-offs that derive from how ‘hot’ code is or whether your debugging or profiling. Examples using assembler code show the radical different optimizations made at different compilation levels. The garbage collector is also an important part, where there is no one perfect solution: performance depends on how willing you are to accept pauses, but also on hardware. Thread local heap performance is improved by allocating more heap space than required (so instead of allocating a few bytes, more is allocated, which can be used for next requests for allocation space). As this may lead to fragmentation, some bookkeeping is performed and above certain thresholds, compaction kicks in. It also addresses the compressed references: larger object references used on 64bit systems decrease performance. By utilizing the fact the objects are 8-byte aligned and realizing that most heaps address at most 32GB, the pointers can be compressed to the same size as on 32bit systems, and it opens some extra benefits on certain platforms as well. Threading and monitoring optimizations attempt to reduce the penalty of Java using monitors everywhere. Optimizations include ‘tasuki locks’. Since monitoring and stability are important, the last GC data etc is dumped on a VM or application crash. Users of the IBM VM should check out ‘health check’.

Another session on performance followed suit, titled ‘Robust and Scalable Concurrent Programming: Lessons from the Trenches’, by people from eBay. It started with the regular blah about concurrency being hard, most developers not fully understanding it, etc. Making scalable software is even harder, as it requires one to understand what happens when the system is under concurrent load and the mechanisms that allow one to make trade-offs. The session went over some some patterns. The first being lazy initialization, showing you should be careful to get it right and that some ways of getting it right do not scale. The best solution is eager initialization, but in some situations you could use the holder pattern or the corrected double-checked locking. Second is the map & compound operation, of which different version are shown to be broken in one way or another. Another pitfall is the use of non-threadsafe classes like SimpleDateFormat (solution: just allocate a new instance or make it thread local). Others are to be aware of hidden costs such as in class.forName() as it takes many locks and walks the classpath: calling it multiple times is not an issue if the class is found, but it becomes a hotspot if the class cannot be found. The conclusion is that thread safety should be considered non-negotiable, after that improve scalability, and usually that involves only fixing a few contended locks. Be both proactive as well as reactive.

Another session on JVM details was ‘Inside Out: A Modern Virtual Machine Revealed’, again a session with Goetz and other smart minds. It went over the advantages of having a virtual machine: the obvious being portability and security. Not so obvious is performance: the VM can choose to apply optimizations not available on all chips. Having a virtual instruction set allows higher level abstractions, and constraining some things leads to more possibilities for optimization. The VM also does dynamic compilation, so the system can profile codepaths and aggressively optimize them. Virtual Method calls served as an example of the optimizations that can be made by the optimizer. Speculative optimization is another thing VMs can do, as well as scalar replacement (sometimes objects are not necessary and can be replaced by some fields in registers). An enabling technique to this is escape analysis. Lock coarsening, lock elision, biased locking (based on information collected at runtime by the profiler) are applied to mitigate the costs of locking. For garbage collection there are techniques such as object relocation, and the fastest path for object allocation can be as low as 10 instructions. These things help cache locality, and can easily outperform malloc and free. Some obscure optimizations are large pages (handling the issue of scarce TLBs) and NUMA awareness, which allows threads to be scheduled at their home-nodes when possible, giving a modest to huge performence improvement. Conclusion is that by giving up some control, we get a lot back.

The session ‘Introduction to Google Guice: The Java Programming Language Is Fun Again!’ by Jesse Wilson was heavily attended. It started with an explanation why direct constructors are bad (harder to unittest and reuse). The common Java way is to use a factory, but this has some downsides (especially the factory version being shown). Google Guice acts as a super-factory, removing the boilerplate code, does more checks and makes it easier to write better code. The presentation described bindings, provider methods, binding annotations (requires a bit of code to define the annotation, but allows the compiler to check, which is not possible with string identifiers) as ways to set up the injection of dependencies. Guice also has the concept of scopes, which determine how many instances will be created, allowing a different/better way to create singletons. For injection, Guice supports constructor injection (the preferred way), method injection and field injection (which you shouldn’t use as it is hard to test). By leveraging Guice, it is easier to maintain modularity. It supports type literals, AJAX, servlets, AOP (method interceptors), and an introspection SPI (with Guice 2.0, cool for graphing dependencies!).

The final session for this year’s JavaOne was ‘How to Write a Distributed Garbage Collector’ (yet another session on deep VM internals). The session posed the hypothesis ‘algorithm design outweighs platform importance’. After the introduction of some concepts and terminology, the actual description of a distributed garbage collector was discussed. The base of the algorithm is a concurrent mark-and-sweep algorithm, where the objects to remove are those not reachable from root objects, not added to the graph while the marking phase was running and not in the Java VM heap. A better collector does generational collection, where a different definition for young and old is used (young is what has never been written to disk (yet), old is what is on disc even if it is in memory too). The generational collector considers only roots that are in memory. It has the benefit of avoiding disk I/O and can therefore run more frequently, but doesn’t clean up the disk (which must be done using a full DGC). The latest GC version takes care of server stripes. Having multiple servers cause that no single machine knows the whole object graph. The new algorithm appoints one server as coordinator and passes a token to other servers when encountering an outbound reference (in an implementation batches of tokens are sent to avoid flooding the network with small requests).

Another great JavaOne has come and gone. It was slightly less crowded, some of previous years sponsors were not present, but there were plenty of interesting sessions and the platform is alive as ever. Let’s hope there will be another JavaOne next year!

This morning’s keynote was presented by Microsoft: their first keynote ever at JavaOne. The lengthy (and a bit boring) introduction highlighted the participation between Microsoft and Sun in various areas. The part on interoperability (project Stonehenge) was more interesting and brought with more energy. The teams at Sun and Microsoft have been working together to ensure different layers of your application can be written in different languages, running on different platforms.

‘The New World: JavaFX Technology-Based UI Controls’ by the Swing team from Sun introduced the new controls in JavaFX. The goals for these controls are ease of use, and creating strong 3rd party control and theme markets. The design of components builds on the MVC pattern, but instead of the ideal where the parts communicate in a one way fashion, the skin/behaviour/model parts can all talk to each other. The JavaFX system now provides a more comprehensive set of UI controls (not complete though). The demo shows that these are really getting there. The team also introduced ‘Caspian’, the new look. It intends to provide applications with a fresh modern look, and be customizable using stylesheets. A demo showed how all components can be branded using just two colours. The library also includes basic charts (pie chart, line chart, area chart, scatter chart, bubble chart, 3d versions of bar and pie charts). Interestingly, the API has been designed to have developers specify the visual properties of the data, together with the data, departing from the Swing way of specifying those separately. Reason given is that FX makes it easy to generate the visual description from data retrieved from for instance a database. The layout system has also been changed: layoutbounds are now by default restricted to the shape (so shadow effects have no influence on the layout). Amy Fowler demonstrated the various concepts using a small demo application. Besides the programmatic layout, container managed layout now also starts taking shape. A few new layout managers were added, and hbox/vbox were fixed. A grid-based layout is still missing.

Related to the previous session was ‘Nimbus: Making Swing Look Sexy!’. Nimbus is a vector based look and feel, added to the platform in JRE 6 update 10. The presentation shows some details, but doesn’t always provide the reasoning behind those. It provided several ways to customize thing like the colour scheme, painters and UIDefaults.

After the last lunch break during which the pavilion is open, I went to the session ‘Where’s My I/O: Some Insights into I/O Profiling and Debugging’. The speaker did a good job of explaining the basic concepts and the history of I/O support in Java. His analysis tool, JPicus, looks very usable. It allows monitoring file I/O, providing useful on the amount of data read from files (including stacktraces of read operations), open files (plus stacktraces of the place where the file was opened), information on deletes, etc.

Brian Goetz and Cliff Click, in my opinion two authorities on this matter, presented ‘This Is Not Your Father’s Von Neumann Machine; How Modern Architecture Impacts Your Java Apps’. Goetz almost immediately went into hyperactive-mode speaking of CPU architectures (CISC, RISC). Then were addressed the reasons why we can’t go faster on serial execution, being: power consumption, the ILP wall, memory bottleneck and speed of light. The instruction level parallelism solution to improving serial performance uses pipelining, caching, multiple-issue, O-O-O, etc etc, which are all solutions that keep getting more complicated, while bringing not too much gain. The biggest issue is cache misses, which have a huge negative impact in the order of a few hundred clockcycles, quickly dwarfing the gains of ILP. To improve memory subsystem performance multiple layers of caches ared used, each getting a magnitude larger as well as slower. To make memory access faster, hardware manufacturers are working on new tricks. These things make it much harder to forecast the exact behaviour than the simple expectations us developers have, as illustrated by Cliff’s simulation of just a few Java instructions. The ultimate solution is to go multicore and not ‘waste’ more transistors on more complex schemes. A variant is chip multithreading, which runs a different thread every cycle, keeping the processor busy while waiting for data from underlying caches. But ultimately as developers, we need to change our mental performance models. We need to think in terms of data, not code. ‘Share less and mutate less’. And unfortunately there are still no good tools for the problems we face (related to the cache).

Another fast paced and entertaining session titled ‘Drizzle: A New Database for the Cloud’, was given by Monty Taylor. It described the goals for this mysql-fork that is intended to run in the cloud. It uses a new protocol, supporting built in sharding, UDP (for updates where you don’t really care if now and then an updated is missed), etc. They aim to reduce the amount of code in the core (down to 300Kloc at the moment). The architecture is very pluggable. Surprisingly security has been dropped by default, as most websites don’t really use it (credentials in the code) and don’t need to pay the cost of the authentication code path. Plugins are available for LDAP and HTTP AUTH.

The host for the afternoon keynote is IBM, presenting their vision, titled ’smarter planet’. They use ‘deep collaboration to drive innovation’, apparently meaning they pay their developers to work on opensource projects. One of those projects is Apache Harmony, the alternative VM. Another thing brought to the table by IBM was websphere extreme scale, providing a high performance caching product.

Java is coming to couch potatoes and the BOF ‘JavaFX Technology for TV: That Other Screen in Your Life’ introduced the details. It discussed the API, architecture, and device specifications. There was little time for demos, and many questions.

‘Creating Professional Rich Client Applications’ was next. Different ways in which layout can fail were shown. Absolute positioning should obviously not be used, but then there is still plenty that can go wrong: resizing containers, different look and feels and internationalization can all mess up the layout if not anticipated (or if you take shortcuts based on the way components look on your screen instead of considering how they should behave). Internationalization is supported in Netbeans out of the box, but enhanced options appear when you add the Swing application framework to your project. The same framework eases the creation of long running tasks. While starting a thread is easy, the framework provides standard hooks and easily ties in a progressbar. The SwingX library provides some additional components to use in your application. Creating new components was shown to be as easy as extending an existing one: then it is also draggable to the form editor. By editing the bean properties for the component, you can help users of the component by removing all unnecessary properties. The session then showed the beans binding API, especially the integration with Netbeans. If I’m not mistaken some of the material was already demonstrated at JavaPolis in 2006.

Today’s final session is ‘Java Programming Language Tools in JDK Release 7′. Many changes, such as modules, project coin, etc, required changes to the tooling. The talk provided details on the way new features like modules have been embedded in the compiler. Type inference bugs are being/have been addressed and the diagnostic messages will be better. A short but fierce discussion sparked when someone mentioned the need for XML output and to output only new warnings. Small changes to JavaDoc and javap were addressed as well.