Using Rails with a legacy database schema – Part 2

Part one of this blog post mini-series showed how to override default table names and primary key names in ActiveRecord model classes, and how to define alias attributes for legacy column names.

This part will discuss some options for primary key definitions in the schema file, which are relevant for legacy schemas, as well as primary key value generation on Oracle databases.

Primary key schema definition

The database schema definition of a Rails application is usually provided in a file called schema.rb via a simple domain specific language.

The create_table method implicitly adds a primary key column with name id (of numeric type) by default.

create_table 'users' do |t|
  t.string 'name', limit: 20
  # ...
end

If the primary key has a different name you can easily specify it via the primary_key option:

create_table 'users', primary_key: 'user_key' do |t|
  t.string 'name', limit: 20
  # ...
end

But what if a table has a primary key of non-numeric type? The Rails schema DSL does not directly support this. But there’s a workaround: you can set the id option of create_table to false, declare the primary key column like an ordinary non-nullable column, and add the primary key constraint afterwards via execute.

create_table 'users', id: false do |t|
  t.string 'user_key', null: false
  t.string 'name', limit: 20
  # ...
end
execute 'ALTER TABLE user ADD PRIMARY KEY (user_key)'

Primary key value generation

On Oracle databases new primary key values are usually created via sequences. The Oracle adapter for ActiveRecord assumes sequence names in the form of table name + “_seq”.  You can override this default sequence name in a model class via the sequence_name property:

class User < ActiveRecord::Base
  self.sequence_name = 'user_sequence'
  # ...
end

Sometimes primary key values are auto-generated via triggers. In this case you need the Oracle Enhanced adapter, which is a superset of the original ActiveRecord Oracle adapter, but with additional support for working with legacy databases. Now you can set the sequence_name property to the value :autogenerated:

class User < ActiveRecord::Base
  self.sequence_name = :autogenerated
  # ...
end

This circumvents the default convention and tells the adapter to not include primary key values in generated INSERT statements.

A coder’s manifesto

A personal manifesto about what I value in developing software and what I think needs to change how we develop software.

Remember the Agile manifesto? What was the most important principle behind it?

User value first

Our highest priority is to satisfy the customer
through early and continuous delivery
of valuable software. – The agile manifesto

If it doesn’t benefit the user it should not be done. This can be a new feature, a better user interface, a clearer wording, better performance, robustness, … Not all improvements have immediate value but they must have a value at some time. If you look at the craftsman project priorities timely delivery has the most user value for me. (Personal footnote: I think this is where the software craftsmanship movement sets the wrong focus: quality is not the most important thing, user value is). But how do you know what the user might need?

Communication is key

Communication in all parts of software development is a must. You need to talk to your users, your fellow developers and other project partners. What often is neglected is the communication part of the code and the documentation. The primary measure of good code is how well it communicates its intent. How clear it is. Many measure code quality with things like testability, low coupling, coverage, metrics. But clarity and communication are by far the most important. If you can understand what the code does and how and why, you are able to change it. I personally believe that not only the statements but also the formatting of the code and the individual expression, the style, is important. Just as in novels and poetry, the typography emphasizes the meaning, the formatting can do this for the code.
Sometimes the why of decisions cannot be expressed in code this is where documentation comes in. If you have a need to document the what or the how, refactor your code. The importance of communication cannot be understated. Often talking with the user first can save you days and weeks of coding. How?

KISS and YAGNI

Simple and easy. As computer scientist we are trained to solve a problem correctly in all its glory. Every corner case is handled and secured by a test. I think to be more successful as a developer we have to unlearn this. (don’t get me wrong: there are places and software where we need this but the majority of software doesn’t need this) How often did I implement a complete version of a solution to later see that only 80% of it was used. The remaining 20% occur once in a lifetime but needed the most of the development time. If we constraint the problem we can save magnitudes of development time and can invest in more user value. And in…

Developer happiness

Some developers trade development productivity for runtime performance. But we don’t want to code in assembler or C. I happily trade runtime performance for productivity. Productivity means happiness. I am happy when I get things done. If I need to improve the performance I can focus on the parts which need it (remember YAGNI?). Programming languages, frameworks and platforms are not just tools, they are and form our ways of thinking. Tools we use have to help us reaching our goals, so…

Testing is important but just a tool

Testing gives me confidence to change code without breaking things. It helps me to avoid regression. Tests are a great tool. But only a means to an end. The program code is more important than tests, so tests should not force me to make compromises in clarity or communication level of the code. Ideally testing environments should be easy to set up and execute. One thing the recent TDD debate showed me is that we need to focus on the goals we have and the problems we want to solve with our tools. The tools we use should take a front row seat. If they need more focus or effort than the benefit they bring something is wrong. We need to constantly assess if the tools help us to reach our goals. So we have to…

Reflect

The last principle of the agile manifesto is to reflect regularly. What can be done better? How to improve? What did we learn? Often this sounds like a chore. Many times the reflection is omitted. Clean code tries to prevent this with daily reflection. But the set of practices and principles is questionable and carved into stone. So what can be done to make reflection more attractive? One of my suggestions is to keep a

Developer handbook

Reading Small Talk Best Practice Patterns (by Kent Beck) I could not help but have a feeling that this is like a personal developer handbook. In it Kent touches many important aspects of programming like composition of methods, naming and formatting. On top of that he describes his personal experiences and opinions in many of the patterns. I found this really valuable. I think starting with some of these patterns and my own experiences it would be helpful to record them in a personal developer handbook. I can use this book to remember past solutions and reflect on them. I can add my experiences in different projects and contexts to these. The goal is to get better at writing clear code and improve the communication of my code. These records could also help me to make my common habits, patterns, mistakes and approaches to problems explicit and learn from them. This is a personal book but it could also be a team effort or help others. The last part, the conclusion, of the TDD debate has a special insight for me: I should not lean on the masters of software development to advance our field and my development skills in particular. I need to find my own way and many things I take for granted I have to…

Re-think

Kent told an anecdote how he discovered TDD and then it struck me: he had a goal (or a need) in mind and had to find his way. In hindsight it sounds easy but it takes courage and persistence to push through. I think many more problems currently exist in developing software and often we took them for a given, we adjusted us, we accepted them. We cannot imagine a solution for these problems because like the elephant with the rope we never experienced a time without them. But this needs to change. We have to rethink the unsolved or inadequately solved problems and ignore some conventions and habits we formed as developers and as an industry. We have to rethink some of our approaches and assumptions. I believe we can find new ways which improve how we develop software and for this we need to rethink.

Recap of the Schneide Dev Brunch 2014-06-01

If you couldn’t attend the Schneide Dev Brunch at 1st of June, here is a summary of the main topics.

brunch64-borderedYesterday, we held another Schneide Dev Brunch at last. The Dev Brunch is a regular brunch on a sunday, only that all attendees want to talk about software development and various other topics. If you bring a software-related topic along with your food, everyone has something to share. The brunch was very well-attended this time. We had bright sunny weather and used our roof garden to catch some sunrays. There were lots of topics and chatter. As always, this recapitulation tries to highlight the main topics of the brunch, but cannot reiterate everything that was spoken. If you were there, you probably find this list inconclusive:

Home office in another time zone

One of our attendees is preparing to leave Germany for at least one year to work in another timezone one the same projects. He gave a quick overview about the setup and some considerations. The team is used to distributed, multi-timezone work, but will now span the whole scala of it. We are eager to have a first-hand report about how it all plays out and sad that we will not see him for quite a time in person. (Personal note: I will miss the developer beer meetings we held infrequently)

XP 2014 conference in Rome

Another one of our attendees just came back from the XP 2014 conference in Rome, still hungover. She reported a lot of impressions and single bits of insights impromptu and will work up a more refined talk for the next brunch. One thing that seems like a really good idea is the “Stop Work Authority Card”. Basically, it’s a card you can hold up like a referee in a sports match to clearly state that the safety of some of your most valueable assets is compromised or risking to be. You have the obligation to play the card if you perceive such a threat and the (temporary) authority to remove it or have it removed.

The idea of “safety” (in non-hazardous or friendly) was a big theme at the conference. The claim that “safety is the prerequisite of excellence” stood out.

The XP 2014 conference was a small one, but visited by insiders from all over the world. It certainly sparked a lot of ideas and food for thought. We are looking forward for the report at the next Dev Brunch.

Is TDD dead?

A most recent discussion we at the Softwareschneiderei follow with great interest is the debate around David Heinemeier Hansson’s frontal attack on the hype around Test Driven Development. There are lots of blog posts to read, some better, some not so much. But an highlight is probably the video chat series between Kent Beck (inventor of TDD), Martin Fowler (general loudmouth, here in a rather quiet role as a moderator) and David Heinemeier Hansson (general firestarter). And while the topic is hot and the discussion fresh, we soon deviated from the main questions and explored the state of art how knowledge and experience is transported in our profession. We concluded that while we all dislike populism, it’s an effective tool to transport messages (with the downside of losing nuances on the way).

Continuous improvement

One attendee asked about good ways to improve his skill and craft. Besides the obvious answers (sleep less, train more, read a lot), there were quite a few ideas. One source of inspiration could be “Jiro Dreams of Sushi”, a documentary movie about a famous sushi master and his quest to perfect the art of sushi (yes, the little snacks that are delicious even without mastery). The concept of “better every day, but never good enough” was identified to be prone to perfectionism, a trait often found in masters of their field, but probably not the most economically sound one. The author of this blog post wrote about his approach to professional passion three years ago.

Radical table

We agreed to consider our little discussion group “the radical table” because we don’t shy away from argueing in the extremes to get our messages across. This all was mentioned in good spirits and without personal insults. But if you read about the “radical table manifesto” some point in the future, don’t be surprised. It might include a plea to Uncle Bob to never give up his style to deliver keynotes and talks even if we don’t attend it twice.

Start-up software tools

In the end of the brunch, we split into several smaller groups to discuss more specific topics of personal interest. I can’t report for the talks I didn’t attend, but joined a discussion about recommendable and necessary tools for a software development start-up company. Some tools that were given included OpenERP, JIRA (including the whole Atlassian portfolio), FogBugz, Microsoft Office 365 and CAS Genesis World.

One controversial topic was the importance of integration (as in “one tool for everything”) versus requirement matching (as in “does exactly what we want”). Related was the topic of “plan ahead” versus “change tools mid-flight”. If you have experience with these questions, please leave a comment.

Epilogue

As usual, the Dev Brunch contained a lot more chatter and talk than listed here. The high number of attendees makes for an unique experience every time. We are looking forward to the next Dev Brunch at the Softwareschneiderei. And as always, we are open for guests and future regulars. Just drop us a notice and we’ll invite you over next time.

Don’t let one bad apple spoil the whole bunch

One exception in a collection operation like for-each or map/collect stops the processing of all the other elements. Instead of letting the whole task blow up it is often more desirable to skip those elements causing failures, log the errors (and possibly notify the user about the failing elements), but have all other elements processed. Examples for such operations are: sending bulk mails to users, bulk import/export, lists in user interfaces etc., and common errors are, for example, NullPointerExceptions, database errors or wrong email addresses.

Here’s some simple code for robust and reusable for-each and map operations in JavaScript:

function robustForEach(array, callback) {
  var failures = [];
  array.forEach(function(elem, i) {
    try {
      callback(elem, i);
    } catch (e) {
      failures.push({element: elem, index: i, error: e});
    }
  });
  return failures;
}

function robustMap(array, callback) {
  var result = { array: [] };
  result.failures = robustForEach(array, function(elem, i) {
    result.array.push(callback(elem, i));
  });
  return result;
}

Similar code can be easily implemented in other languages like Java (especially with Java 8 streams), Groovy, Ruby, etc.

If you decide to log the errors, you have to choose between two possible log strategies: one log operation per error, which can be annoying if you get a mail for each logged error, or one log operation bundling all occurred errors (make sure that a failing toString can’t spoil the whole bunch again).

function logAny(failures) {
  failures.forEach(function(fail) {
    log.error(failMessage(fail));
  });
}

function logAnyBundled(failures) {
  if (failures.length == 0) {
    return;
  }
  log.error(failures.map(function(fail) {
    return failMessage(fail);
  }).join('\n'));
}

function failMessage(fail) {
  return "Could not process '" +
         fail.element + "': " + fail.error;
}

You can easily combine the map and log operations:

function robustMapAndLog(array, callback) {
  var result = robustMap(array, callback);
  logAny(result.failures);
  return result.array;
}

Example usage:

var numbers = [1, 2, 3, 4, 5, 6, 7, 8];
var result = robustMapAndLog(numbers, function(n) {
  if (n == 5) {
    throw 'bad apple';
  }
  return n * n;
});
print(result);

// Error log output:
//  Could not process '5': bad apple
// Output:
//  [ 1, 4, 9, 16, 36, 49, 64 ]

One element could not be processed due to an error, but all other elements were not affected.

Conclusion

Be aware of the bad apple possibility for every loop you write (explicitly or implicitly) and consciously choose the appropriate error handling strategy depending on the situation. Don’t let indifference decide the fate of your bulk operations.

How the most interesting IT debate is revealing our values as software developers

TDD is dead. Is TDD dead? A question that seems to divide our profession. What does this debate have to do with you?

TDD is dead. Is TDD dead? A question that seems to divide our profession.
On the one side: developers which write their tests first and let them drive their code. They prefer the mockist approach to testing. Code should be tested in isolation, under lab like circumstances. Clean code is their book. Practices and principles guide their thinking. An application should not be bound to frameworks and have a hexagonal architecture. The GOOS book showed how it can be done.
On the other side: developers which focus on readability and clarity. They use their experience and gut to drive their decisions. Because of past experiences they test their the code the classical way. They are pragmatic. Practices and principles are used when they improve the understanding of the code. Code is there to be refactored. Just like a gardener trims bushes and a writer edits his prose they work with their code.

What are your values?

What does this debate have to do with you?

Ask yourself:
What if you could write a proof of your program costing 10 or just 5 times as much as the implementation? It would prove your code would work correctly under all possible circumstances. Would you do it?

Or would you rather improve the existing architecture, design or clarity of your code? So that you remove technical debt and are better positioned for future changes.

Or would you write new features and improve your application for the people using it?

What are your values?

History

At the beginnings of my developer life in the late 80s/early 90s I remember that the industry was focussed on one goal: code reuse. Modules, components, libraries, frameworks were introduced. Then patterns came. All of that was working towards one side of the equation: low coupling.
High cohesion was neglected in pursuit of a noble goal. But what happened? The imbalance produced layer after layer, indirection after indirection, over-separation and over-abstraction. You had to deal with dependency injection (containers), configuration, class hierarchies, interfaces, event buses, callbacks, … just to understand a hello world.
Today we have more computing power and are solving more and more complex things. We think in higher abstractions. Much more people benefit from our skills and our works.
On the user facing side design focusses on simplicity and usability. Even complex relationships can be made understandable and manageable. A wise man once said: design is about intent.
The same with code: Code is about intent. Intent should be the measure of the quality of our code. Not testability, not coupling: intent. If the code (and this includes the code comments) would reveal its intent, you could fix bugs in it, improve it, change it, refactor it. Tests would be your safety net to ensure you are not breaking your intent.
You might say: but this is what TDD is all about! But I think we got it all backwards. The code and its intention revealing nature is more important than the tests. The tests support. But tests should never replace or even harm the clarity of the code.
The quality of the code is important. But most important are the people using your application.
My goal is to delight the people who use my software and my way there is writing intention revealing software. I am not there and I am learning every day but I take step after step.

What are your values?

A hierarchy of project needs

We all know Maslow’s pyramid, so why not apply the idea to the needs of a software development project (note: not the developer of the project!).

A few weeks ago, I traded stories with a fellow software developer when he told me this little gem: A developer programs a web shop that looks pretty and runs smooth. But as soon as you place multiple items in the shopping cart, you’ll inevitably end up with an amount of XX.999999999998 euros (or whatever currency you want). When asked why the shopping cart “computes the wrong amounts”, the developer answered that the amount is correct and that’s just the way a floating point number behaves. He didn’t see a problem with the functionality. My immediate answer: “Wow, that’s very low on the Maslow pyramid”. We both understood, but since then, I tried to come up with a Maslow-like pyramid that would explain my sentence to a larger crowd. So here is how my attempt has grown so far.

Maslow’s hierarchy of needs640px-Maslow's_Hierarchy_of_Needs.svg

Abraham Maslow was an american psychologist that studied mental health and human potential. He invented an hierarchy of human needs that is also known as Maslow’s pyramid. On a side note, he also pointed out the human tendency to over-apply known tools. His pyramid has five stages (IT people would call them layers) of human needs that begin with the very basic ones (e.g. air, water) and scales to the abstracts like morality and creativity. If something is “low on the pyramid”, then it can be seen as granted by priviledged people. Most of us never think about our air supply requirements. Everything “high on the pyramid” can be seen as “expendable” in times of crisis. Morality will be forgotten as soon as we seriously lack water.

A hierarchy of project needs

My immediate answer to the story in the introduction suggested that I think an equivalent pyramid exists for the needs of a software development project. And a quick research on the internet reveals that I’m not the only one with that idea. For example, Scott Hanselman blogged about it in 2012, and Francis Shanahan came up with an extended version in 2009. Both adaptions are reasonable and stand on their own – I don’t want to invalidate or change them. Instead, I publish my attempt as an addition to the discussion, if there is any.

Here is my five-layered pyramid of project needs:

project maslovLayer 0: Executable

Let’s face it: If your project doesn’t compile or crashes right after being started, it isn’t much worth. And just because it runs on your machine doesn’t make it any more useful to others. So the most basic need a project has is to be executable on the target machine. This includes some form of correctness – if your program doesn’t perform the right operations, it can run indefinitely and not provide any value. Please note that the program doesn’t have to be bug-free or tested to be useful. It just has to adhere to the intended use case. In our introduction story, the web shop looks pretty and runs smoothly. It certainly is “Executable”.

Layer 1: Abstraction

This is where I placed the mishap in the introduction story. Every project needs some form of abstraction or separation between the internal representation of data and functionality and the external presentation to the user. This is probably trivial to most of you, but I’ve seen way to much code that uses external presentations (e.g. strings from the GUI) to make important decisions and others have, too. A key rule is “once data is formatted, it is eternally lost and unavailable to computing / data processing“. The rule for the other way is that you should never present data without proper (human-readable) formatting. The amount of work you save by not pretty-printing (formatting is just the formal term for adding syntactic sugar to make the data edible for humans) is largely offset by the amount of work your users will have to invest to decipher the output.

Layer 2: Architecture

You can call it design, architecture or whatever you like, any reasonably large code base needs some kind of structuring that prevents it from imploding. A whole theory of patterns was invented to keep code aerated enough to prevent it from decomposing to compost. And we all know what compost code looks and smells like. Applying architecture to your code keeps it maintainable and refactorable and in outstanding cases even modularizable. This is the layer where most projects fail on the long run. Even if at first there was a design, it gets watered down with every modification. Good principles to counter this effect are the “no broken windows” approach and the boy scout rule.

Layer 3: Verification

There is a moment in programming when you hand your code over to the next developer. Usually, this moment is called “commit” (if you don’t use version control, have a good look at Scott Hanselman’s lowest pyramid layer!). Oftentimes, the next developer is future you – and you have no clue what past you thought when he wrote that crap. You can’t even distinguish between features and bugs. That’s why your project wants verification. It’s not utmost important if you verify your code with unit tests, integration tests, acceptance tests, contracts or all of them together. It’s important that your code is accompanied by automated guardian angels that catch the most dangerous accidental modifications and help to point out the bugs among the features. Automated verification tells future you that whatever past you wanted to build, it’s still intact. This layer is the life insurance for functionality as much as the architecture layer was for code.

Layer 4: Style

Every program in the world can still do its job properly even if we would eliminate everything “stylish” in their codebase. Style is the most human-centered need in the pyramid. No machine or compiler has yet developed aesthetic likings. Scott Hanselman called this layer “bragging rights”, another thing computers don’t care about. This is the level where most bickering among developers takes place, but it’s also the level that can most easily be ignored without sacrificing critical project needs. Or, to put it bluntly: Your project most likely doesn’t care half as much about style as you do.

Where to go from here?

My most important message with the hierarchy of project needs is that we often focus on the higher needs and take the lower ones too much for granted. If your code lacks in the fundamental layers, the damage is much greater in terms of project value. A stylistic displeasing code will hurt the next developer, but a code lacking abstraction will hurt every user of your software, as exemplified by the story in the introduction. As we developers should be the advocates of our project’s needs, we have to think more in regard of its benefit than our personal self-actualization. But the required traits to do so properly aren’t even on the original Maslow’s pyramid, so it’s a big challenge for any of us.

Translating strings in internationalized applications

Internationalization (“i18n”) and localization (“l10n”) of software is a complex topic with many facets. One aspect of internationalization is the translation of strings in programs into different languages.

Here’s an example of how not to do it (assuming t is a translation lookup function):

StringBuilder sb = new StringBuilder(t("User "));
sb.append(user.name());
sb.append(t(" logged in "));
sb.append(minutes);
sb.append(" ");
if (minutes == 1) {
    sb.append(t("minute"));
} else {
    sb.append(t("minutes"));
}
sb.append(t(" ago."));
return sb.toString();

Translatable strings and concatenation don’t mix well, be it via StringBuilder, the plus operator or in template files like JSPs. Different languages have different sentence structures. You can’t know in advance in which order the parts must appear in the translated text. So the most basic rule is: never construct sentences programmatically from sentence fragments if they are intended for translation.

Here’s a slightly better variant:

if (minutes == 1) {
    return t("User {0} logged in {1} minute ago.", user.name(), minutes);
}
return t("User {0} logged in {1} minutes ago.", user.name(), minutes);

I18n frameworks always offer the possibility to pass arguments to the translation lookup function. This way translators can freely choose the positions of these arguments via placeholders in the translated string.

However, not all languages have pluralization rules similar to English, where you have to handle only two cases (one and zero/many). For example, Russian and Polish use different forms of nouns with different numerals higher than one. Here’s an extensive table listing the plural rules for different languages: The rules are classified into these categories: “one”, “two”, “few”, “many”, “other”. Good i18n frameworks provide translation lookup functions where you can pass the count as an additional argument. The framework then dispatches to different translation keys, depending on the count and the target language:

user.login.minutes.one=...
user.login.minutes.two=...
user.login.minutes.many=...
user.login.minutes.other=...

There are other traps that you have to watch out for, e.g.

  • different punctuation marks: you can’t simply assume that you can convert any translated text into a label by appending “:” to it, or that you can convert any translated text into a quotation by surrounding it with ” and “.
  • gender rules, which can be handled similarly to the pluralization rules

Conclusion

This article gave a small glimpse into the topic of internationalization, to help avoid the most basic mistakes. Check out the documentation of your internationalization framework to see what it can offer.

Look into the past, become more agile: egoless programming

Agile software development methods like extreme programming and Scrum have been around for almost 20 years now. Many think of them as “the right way” or some kind of “holy grail”. So it is no wonder that many companies try to hop on the agile train to improve quality and efficiency of their software development.

Why is it that I hear of failures in adopting/switching to agile most of the time?

In my experience there are two main reasons why implementing agile methods does not work as expected:

  1. It is the management deciding to change the development process, not the developers. After a short while many aspects – especially using rigid methods like Scrum – do not seem to fit the organisation and therefore are changed. This leads to process implementations like ScrumBut
  2. Many developers do not have the mindset for the interactive, open and collaborative work style required by agile methods. Too often developers try to secure their job by isolating themselves and their solutions. Or they are doing stuff the way they are used to for many years not willing to learn, change and improve. Communication is hard, especially for programming nerds…

What can be done about it?

I would suggest trying to slowly change the culture in the company based on concepts from the 1970’s: egoless programming. In essence you have to let developers become more open and collaborative by internalising the Ten Commandments of Egoless Programming:

  1. Understand and accept that you will make mistakes.
  2. You are not your code.
  3. No matter how much “karate” you know, someone else will always know more.
  4. Don’t rewrite code without consultation.
  5. Treat people who know less than you with respect, deference, and patience.
  6. The only constant in the world is change.
  7. The only true authority stems from knowledge, not from position.
  8. Fight for what you believe, but gracefully accept defeat.
  9. Don’t be “the guy in the room.”
  10. Critique code instead of people—be kind to the coder, not to the code.

There is a PDF version of the commandments with some amplifying sentenctes from Builder.com published on techrepublic in 2002. If you manage to create a development culture based on these values you are more than half-way down the agile road and can try to implement one of the popular agile methods – or your own!

Developer power tools: Big O = big impact

Scalability and performance are often used interchangeable but they are very different. The big O notation helps in talking about scalability.

Scalability and performance are often used interchangeable but they are very different. The resource consumption of a program is its performance. So performance looks at a specific part of a program, say the user activating an action and tries to fix the input and circumstances.
Scalability defines how the resource consumption of a program changes when additional resources are added or the input size increases. So a program can have good performance (it runs fast) but when the load increases it can behavely badly (a bad scalability). Take bubble sort for example. Since the algorithm has low overhead it runs fast with small arrays but when the arrays get bigger the runtime gets worse. It doesn’t scale.
There are many ways to improve scalability here we look at one particular: reducing algorithmic complexity. The time complexity of an algorithm is measured with the big T notation. The T notation describes the time behavior of the algorithm when the input size changes. Say you have an algorithm that takes n objects and needs 4 times as long with an overhead of 2. This would be:

T(n) = 4n + 2

Often the correct numbers are not necessary, you just want to have a magnitude. This is where the big O notation comes into play. It describes the asymptotical upper bound or just the behaviour of the fastest growing part. In the above case this would be:

T(n) = 4n + 2 = O(n)

We call such an algorithm linear because the resource consumption grows linear with the increase in input size. Why does this matter? Let’s look at an example.

Say we have a list of numbers and want to know the highest. How long would this take? A straight forward implementation would look like this:

int max = Integer.MIN_VALUE;
for (int number : list) {
  if (number > max) {
    max = number;
  }
}

So we need if the size of the number list is n we need n compare operations. So our algorithm is linear. What if we have two lists of length n? We just our algorithm twice and compare both maximums so it would be

T(n) = 2n + 1 = O(n)

also linear.
Why does this all matter? If our algorithm runs quadratic, so O(n^2) and our input size is n = 1000, we need a multitude of 1 million operations. If it is linear it just needs a multitude of 1000 operations, much less. Reducing the complexity of an algorithm can be business critical or the difference between getting an instant result or losing a customer because he waited too long.
Time complexity isn’t the only complexity you can measure other resources like space can also be measured with big O. I hope this clears some questions and if you have further ones please feel free and leave a comment.

Gigapixel images in pure Java

What you can do when you hit an ancient limitation of Java while working with gigapixel sized images.

Not long ago, I read this nice little blog entry about the basic properties and usages of Java arrays. It’s a long time since I last used an array in Java myself, because my programming style evolved to heavily leverage the power of collections (and Iterables in particular, the Java 5 poor man’s substitute for Java 8 Streams). But I immediately noticed that one important fact was missing from the array blog entry:

The maximum length of an array in Java is Integer.MAX_VALUE or ((2^32)-1), aka 2.147.483.647

This is indirectly specified in the Java language specification, chapter 10.4 Array Access:

Arrays must be indexed by int values.

This little fact crossed my path when writing a little tool in pure Java that operated on large numbers of large images, combining them to a gigantic image. The customer used the tool to create images that had a size of about 100 MB, but took several hours to print because the decompression tax kicked in. One day, he reported a strange bug:

array-error-cropped

 

“Oh, a negative array size, what a strange bug to appear in a tested application” was my first thought. Only after reading the stacktrace more carefully did it dawn on me: The array size wasn’t negative, it was just bigger than Integer.MAX_VALUE and got wrapped around into the negative numbers. And sure enough, 72350 times 44914 is a respectable 3.249.527.900 pixels, more than 1,5 times as much as an array in Java can hold. This image was right in the multi-gigapixel range where all kinds of technical obstacles appear. The maximum length of an array in Java was mine.

Trying to stay pure

One cornerstone of the tool was being lightweight. It shouldn’t carry around unnecessary luggage and weighted around 200 kB when the bug appeared – enough to just copy it into the data directories instead of pulling the directories into the program. But when I examined the root cause of the problem at hand, I found the frustrating truth that Java’s built-in imaging library also relies on one cornerstone: all data is stored in one array. And this array can only hold around 2G entries of data.

My approach was to “partition” the full image into smaller parts that only stored a fraction of the overall pixels. To hide this fact from the ImageIO that ultimatively writes all the data into one file, my PartitionedImage implements RenderedImage and has to translate every call into a series of appropriate subcalls to the partition images. Before we look at some code, let me show you the limitations of this approach:

Greedy JPEGs, credulous PNGs

In the RenderedImage interface, there are two methods that can be used to obtain pixel data:

  • Raster getData(): Returns the image as one large tile (for tile based images this will require fetching the whole image and copying the image data over).
  • Raster getData(Rectangle rect): Computes and returns an arbitrary region of the RenderedImage.

If an image writer calls the first method, my code is screwed. There is no mentally sane way to construct a Raster instance without colliding with the array length limitation. Unfortunately, the JPEG writer does just that: He gets greedy and demands all the pixels at once. I found it easier to avoid the JPEG format and therefore trade disk space for pragmatism.

The PNG writer uses the getData(Rectangle) method to obtain the pixel data. It calls the whole image line by line: the region has always the full width of the image, but is only one pixel in height. So I guess my tool will write a lot of large PNG images in the future.

Our partitions should adapt to this behaviour by always retaining the full width of the original image and only allowing enough height that the amount of pixels per partition doesn’t exceed Integer.MAX_VALUE.

The remaining trick is to implement an AdjustingRaster that knows the original Raster of the partition and translates the row asked by the PNG writer to the according row in the partition image. The AdjustingRaster needs to know about the vertical offset. The only pitfall here is that the vertical offset has to be zero while the AdjustingRaster gets written to and needs to be set once it switches into read mode.

Slow, but working

By composing a gigapixel image from several partitions (sometimes called tiles) you can circumnavigate the frustrating limitation of Java’s arrays (I mean, it’s 2014 and 64-bit systems are somewhat prevailing now. No need to stick to 32-bit limits without a good reason). The result isn’t overwhelmingly fast, but I suspect that’s caused by the PNG image writer more than by our indirections. And we shouldn’t forget that it’s a lot of pixels to write after all.

Conclusion

Sometimes when you explore bigger and bigger use cases, you hit some arbitrary limitation. And some are fundamental ones. In our case here, we’ve reached the limit of Java arrays and got stuck because the image library in Java never heard of real gigapixel imaging and coupled itself hard to the array limit. By introducing another indirection layer on top of the image library implementation and using composition to emulate a bigger image than we actually could create, we can convince non-sceptical image writers to save all those pixels for us and even manipulate the image beforehand.

What was your approach for gigapixel image processing? How did it work out in the long run? Share your story in the comments, please.