Ready, Set, GO! Putting Threads to Race lightcycles in the JVM. Getting to a lock-free implementation

Lately I have been trying to improve my skills on lock-free algorithms. So I have been studying the literature and the javadoc of the atomic package. But I also felt that I needed to apply them on a concrete programming exercise to actually do progress grasping the important concepts. So I was trying hard to come up with an idea, but for some reason I couldn’t. This changed during last week’s Heinz’s happy hour webinar. At some point a comment by Piotr Findeisen prompted Heinz to talk about “racing threads”, “which thread won and did them all”. All this talk triggered my imagination and I somehow visualized LightCycles from the Movie Tron racing against each other playing chicken. 🙂

This post is about how I implemented a set of program in Java that models this imaginative scenario using two Threads and how I though it through to eventually get to one which uses a lock-free algorithm. I decided to share this for two reasons:

  • One because I found it quite cool to work on this, and would have loved to read it myself! 🙂
  • Secondly I am hoping this will prove helpful to others trying to think on these topics. I had quite some trouble reasoning about this so I will try to explaine how I thought about it and reached a solution that seems to work!

Continue reading

Making powerline fonts work inside IntelliJ IDEA terminal

Intro

You can skip down to the steps if you are not interested to know how I came to need this ;).

I happened to watch Dan North’s Power use of UNIX video where he talks about zsh. I have been using bash for almost 2 decades which felt like a good milestone to look into a new shell so I decided to explore it. This led to an old fashioned web serfing session, and after a few links, going through Oh My Zsh, I discovered the cool powerline based themes that caught my eye. Out of the box, the characters do not work and I found that I needed a bit of tweaking with my fonts to make them work.

Continue reading

Refactoring Inheritance to Composition. A practical step-by-step example.

While experimenting for my previous Sparse Array post I wanted to be able to easily change between using a HashMap and a Sparse Array approach in my code so I would be able to quickly make measurements with both. To achieve this at the time I thoughtlessly came up with an inheritance approach. At the time I thought that it would be better to be refactored to composition but because I liked the idea to do the refactoring and describing it in a post I decided to leave it for later. And this later time has come! 🙂

Continue reading

Growing an automated test development culture in your organization. Ideas on how to get there.

We had our first meet of the year http://www.meetup.com/Thessaloniki-Java-Meetup-Group/events/234154914/ of the Thessaloniki Java Meetup Group. BTW  I greatly enjoyed the talk. I always feel like a true weirdo when using multiline bash one-liners in my daily work:) . It was nice to see that I am not the only one doing that!

My thanks to Prof. Spinelis! @CoolSWEng

During the Q&A part of the talk one of our members, Dimitris Keramidas made a really interesting question that got me thinking. I have known many developers that have pondered upon this question – me included. If I remember correctly Prof. Spinellis had mentioned how we could use an automated testing infrastructure to help when debugging and in general how useful an automated testing culture is to the process of developing software. The question was something along the lines of the following:

Since testing is so useful, we who work in organizations that do not use it, how can we convince our manager, project manager, BA, bosses, stakeholders that doing testing is a useful thing and  convince them to adopt it in our work?

Continue reading

Replacing HashMap with a Sparse Array as an optimization for my Tree String Index.

At my previous post : A tree data structure for String indexing solving a phone-in TV quiz. I talked about how I was satisfied with the performance populating the tree and doing searches. But I was still thinking about how I might be able to make it faster. A key component of the tree is the mechanism that stores the references to next level nodes mapped to a character. In my first implementation I used a HashMap<Character, Node> to store this information. So I had the idea that maybe using a sparse array to store these references would be a better fit. I have implemented it and following are the  results. But let me talk a bit about sparse arrays first. Continue reading

A tree data structure for String indexing solving a phone-in TV quiz.

The premise

Last Friday when I was in the gym doing my cardio warm up on the cardio theater’s screens it was playing  a phone-in game show. The quiz that the players were asked to solve was to find a word, the letters of which were presented jumbled up. The gym’s owner was there and we tried quite hard to find the answer but after a few minutes we gave up, recognizing that is indeed a very hard problem. We exchanged some comments about how in earth is it possible for people to pay all that money to phone in trying to find the right answer and then getting in a lottery to win a small prize. After that the owner was called to attend to something and I was left alone.

The first try

Having 10 more minutes on this very boring part of my workout I started to think. How could I solve this problem using a computer. There must be a database of all the Greek words that I can search on? My first though was to take all the permutations of the letters and search them against the word database but then I counted the number of letters which were 12. Thinking the number of possible permutations would mean factorial of 12 possibles to check. But wait… factorial can get huge fast so no, that would probably not work. (I run the numbers at home and actually 12! = 479,001,600 !).

Continue reading