Tag: java

The Great Rational Explosion

A Dream to good to be true

A few years back I was doing mostly computational geometry for a while. In that field, floating point errors are often of great concern. Some algorithms will simply crash or fail when it’s not taken into account. Back then, the idea of doing all the required math using rationals seemed very alluring.
For the uninitiated: a good rational type based on two integers, a numerator and a denominator allows you to perform the basic math operations of addition, subtraction, multiplication and division without any loss of precision. Doing all the math without any loss of precision, without fuzzy comparisons, without imperfection.
Alas, I didn’t have a good rational type available at the time, so the thought remained in the realm of ideas.

A Dream come true?

Fast forward a couple of years to just two months ago. We were starting a new project and set ourselves the requirement of not introducing floating point errors. Naturally, I immediately thought of using rationals. That project is written in java and already using jscience, which happens to have a nice Rational type. I expected the whole thing to be a bit slower than math using build-in types. But not like this.
It seemed like a part that was averaging about 2000 “count rate” rationals was extremely slow. It seemed to take about 13 seconds, which we thought was way too much. Curiously, the problem never appeared when the count rate was zero. Knowing a little about the internal workings of rational, I quickly suspected the summation to be the culprit. But the code was doing a few other things to, so naturally my colleagues demanded proof that that was indeed the problem. Hence I wrote a small demo application to benchmark the problem.

The code that I measured was this:

Rational sum = Rational.ZERO;
for (final Rational each : list) {
    sum = sum.plus(each);
}
return sum;

Of course I needed some test data, that I generated like this:

final List<Rational> list = new ArrayList<>();
for (int i=0; i<2000; ++i) {
    list.add(Rational.valueOf(i, 100));
}
return list;

This took about 10ms. Bad, but not 13s catastrophic.

Now from using rational numbers in school, we remember that summing up numbers with equal denominators is actually quite easy. You just leave the denominator as is and add the two numerators. But what if the denominators are different? We need to find a common multiple of the two denominators before we can add. Usually we want the smallest such number, which is called the lowest common multiple (lcm). This is so that the numbers don’t just explode, i.e. get larger and larger with each addition. The algorithm to find this is to just multiply the two numbers and divide by their greatest common divisor (gcd). Whenever I held the debugger during my performance problems, I’d see the thread in a function called gcd. The standard algorithm to determine the gcd is the Euclidean Algorithm. I’m not sure if jscience uses it, but I suspect it does. Either way, it successively reduces the problem via a division to a smaller instance.

What does this all mean?

This means that much of the complexity involved happens only when there’s variation in the denominator. Looking at my actual data, I saw that this was the case for our problem. The numbers were actually close to one, but with the numerator and the denominator each close to about 4 million. This happened because the counts that we based this data on where “normalized” by a time value that was close, but not equal to one. So let’s try another input sequence:

final Random randomGenerator = new Random();
final List<Rational> list = new ArrayList<>();
for (int i=0; i<2000; ++i) {
    list.add(Rational.valueOf(4000000, 4000000 + randomGenerator.nextInt(2000)));
}
return list;

That already takes 10 seconds. Wow. Here’s the rational number it produced:

10925412090387826443356493315570970692092187751160448231723307006165619476894539076955047153673774291312083131288405937659569868481689058438177131164590263653191192222748118270107450103646129518975243330010671567374030224485257527751326361244902048868408897125206116588469496776748796898821150386049548562755608855373511995533133184126260366718312701383461146530915166140229600694518624868861494033238710785848962470254060147575168902699542775933072824986578365798070786548027487694989976141979982648898126987958081197552914965070718213744773755869969060335112209538431594197330895961595759802183116845875558763156976148877035872955887060171489805289872602037240200456259054999832744341644730504414071499368916837445036074038038173507351044919790626190261603929855676606292397018669058312742095714513746321779160111694908027299104638873374887446030780299702571350702255334922413606738293755688345624599836921568658488773148103958376515598663301740183540590772327963247869780883754669368812549202207109506869618137936835948373483789482539362351437914427056800252076700923528652746231774096814984445889899312297224641143778818898785578577803614153163690077765243456672395185549445788345311588933624794815847867376081561699024148931189645066379838249345071569138582032485393376417849961802417752153599079098811674679320452369506913889063163196412025628880049939111987749980405089109506513898205693912239150357818383975619592689319025227977609104339564104111365559856023347326907967378614602690952506049069808017773270860885025279401943711778677651095917727518548067748519579391709794743138675921116461404265591335091759686389002112580445715713768865942326646771624461518371508718346301286775279265940739820780922411618115665915206028180761758701198283575402598963356532479352810604578392844754856057089349811569436655814012237637615544417676166890247526742765145909088354349593431829508073735508662766171346365854920116894738553593715805698326801840647472004571022201012455368883190600587502030947401749733901881425019359516340993849314997522931836068574283213181677667615770392454157899894789963788314779707393082602321025304730355204512687710695657016587562258289968709342507303760359107314805479150337790244385189611378805094282650120553138575380568150214510972734241803176908917697662914714188030879994734853772797322420241420911735874903926141598416992690859929943631826094723456317312589265104334870907579391696178556354299428366394819280011410287891113591176612795009226826412471238783334239148961082442565804292473501012401378940718084589859443350905260282342990350362981901637062679381912861429756544396701574099199222399937752826106312708211791773562169940745686837853342547182813438086856565980815543626740277913678365142830117575847966404149038892476111835346566933160119385992791677587359063277202990220629004309670865867774206252830200897207368966439730136012024728717701204793182480513620275549665094200202565592742030772102704751736850897665353297536494739059325582661212315355306787427752670613324951121097833683795311514392922347268374097451268196257308005629903372871471809591087849716533132440301432155867780938535327925645340832637372702171777123816397448399703780105396941226655424025197472384099218081468916864256472238808237005121132164363385877692234230678011184351921814453560033879491735351402997266882544304106997065987376103362395437737475217181551336569975031721614790499945872209261769951117223344186839969922893394319287462384028859822057955389124951467203432571737865201780344423642467187208636881135573636815083891626138564337634176587161231028307776960866522346008589607259041199676560090157817882260300414906572885890188984036234226505815367029839231023461597364977306399898603903392434756572392816540125771578189640871020070756539777101197151773304409519870643142190955018579914630314940373832858007535828153361236115553577694543503842444481599944319287815162136101362705211937257383677282014480487759786222801447548899760241829116959865698836386442016721709983097509675552750221989521551169512674725876581185837611167980363615880958917421251873901289922888492447507837290336628975165062036681599909052030653421736716061426079882106810502703095803882805916960831442634085856041781093664688754713907512226706324967656091109936101526173370212867073380662492009726657437921033740063367290862521594119329592938626114166263957511012256023777676569002181500977475083845756500926631153405264250959378833667206532373995888322137324027620266863005721216133252342921697663864807284554205674829658250755046340838031118227643145562001361542532622713886266813492926885236832665609571019479812713355021295737820773552735161701716018010606040731647943600206193923458996150345093898644748170519757957470535978378479854546255651200511536560142431948781377187548218601919108870420102025378751015728281345799655926856602543107729659372984539588835599345223921737022220676709028150797109091782506736145801340069563865839397272145141831011878720095142353543406658905222847479419799336972983678887227301846161770296173667855239714987183774931791306562351516152727523242208973614372214119191610954209164193665209038399568256186789865817560942946289864468805486432823029457193832616134050058472575/5464071367689021145920376789564097484075057036929154325361292811121525852598101325663975897893163034606703637232625465056851133763148192531586105963101428155647567490545647427502233159652310898001125892675829093187577533366895512701590739143174316498475076791171065480136546725008720643752948237443019242161669077663609144434306128221503414531394096823915215979623953337930493605186601571769495144894636986997575880131117237208510857818613219593393080298986414277944012186244301930294333213815805316754678940597177696108355782072853392533822105101007621252067159549391148948251225551745385134586065334994558336331772298542454065874623247283672363609435360051294428160464673413148011783297358303182389731822629550376618544475198010869325105825675331154332311829064320240772190873197445422806128724029723364642376469088090535867746031708415054086042362900835830071439066729248803080864979591431807735444694059982355674331452510436222691302473693502522151731546119758216043039918795122874474779117841250524168339597048231340441394931963429195108468364711206679388129543777587115734312812004999951805288552516345754609724336541283126925634054615621607387407977448299658305191245949844785795188192329587881827885708672142850022336110188979606923986247270824545988992712993364088907981140326036171066083995899655482025878782401213185589085533281898090985040136079388970812804900747496605542168328539571899508434943602485570225905907644120282314027462195035830426406664327228058856521800556952281791943493734276488880843046612364784975328644388569123725347247071532065625240062618476483177429385912626131806870421725932016173249912942914992853735756415323674217279068679145528740177762103447741638280753518805769821177202801618302946904761889981101239141113424330262556585926281757788049928339119700279137278143586150134536970549327847433827708642630282821305576285238510965599311560018270085653975154329160951814845203648945184348538132528313719965960517692615234724933839415863834082163365616979319651204331888160659534780756175312928937580725581177783203569550625979825708835192412739747467314045215372710237518236109496682610777837094944201522879675742349874447002866525687741559327659019423524782141050034563799707395461801978917300210616390761873065433809737256362778865972956861423012424858347791919074000867019988914246185988825680768363450694954357708832975385526022445613099402197649574980990392753660371969220370462447697883319180076033708570759874351259644698980354866068784429511482751711329624930863629304545443308117342612677534958727764219861540475648492451312505519760969766401341016292089564143516344584197883268917604454917829927706134205489288603918892893943815239131020894621190795863599245502858307692284626604530452680973144088318876770254624083735638792267234407991769552946582638360068875509975769002847311018204789400549401560376453753063628076240879327047662612561558831502017122298425734701863181656884664851026481979959368508273072349808416302081774935491159815938813047108294310775621375475681754627108394755080076400344634873409823122370888409229666662703837096634538759103222727447751640114800586463155863216558367921497862783396136480309101772689723377535772396361300263399246855706948606216922101060308941294672554277063185792769730719177469014803853068307966008447841184403910224016078072279882935920347299431580783664128991812654780457701135185591782941754395263461459180940761928488860853515685525983743168631933069310771834569879795160576216776499263300025539821575767674288253419696114910586812284230709422230558006531335540918025940397918186306383352682903150594714754889631368556569576312855831657674738769087018659290558967429709446878600756119596020561987088170551193295467295484037656684414413021143993266548616775075905905925334335921152629477697210074629622902141063078657746149232034056642352265941452947845339051610301151130368316362022636711499114826671695540416257477345744126416363795225938900727969092692270788643742709421442552812735921534532156766228688341300473140115855278302077136595142902548557943030527129378779996403263450119984758775332533036452077654603781557033976641416371186050927154435643492983848051087282942559503555223474754690693742997370592039106889187781827888290578576160100274561900208861136548215743616634615083974725330617020874519606610812580339985836584711397102753448160446984238925180319975660479580098047098930179253806342651446549086560273369490291496196263969077175524002077318170194252067818804991902015489300563029607689935067689448990111925784018672159126316019672778424331051001652240822592173809393561688768265941132515679297537471384753992855568256114701369550476003237008840508060572457453896791033992685192069703595482787771374051189250065726225137532026227150630791972777126392521002221370419505711150022179216266239656298115575018443700688208844387102582445812545858014862427316785193110884751319467750425511273629581416588296942433219322216784262821066075700266485645060935996743388485096744598169509920624971167075214788838073469621687619355816573640360338756385397428237445511332615921133308459043700086925442114337299109227541364012352140312577797531234832237279430947774637533319353713938562360646441591033255036

I kid you not, that’s over 10000 digits! In the editor I’m writing this in, that’s roughly 3 pages. No wonder it took that long. Let’s use even more variation in the numbers:

final Random randomGenerator = new Random();
final List<Rational> list = new ArrayList<>();
for (int i=0; i<2000; ++i) {
    list.add(Rational.valueOf(4000000 + randomGenerator.nextInt(5000),
            4000000 + randomGenerator.nextInt(20000)));
}

Now that already takes 16 s, with about 14000 digits. Oh boy. Now the maximum number of values I expected to do this averaging for was about 4000, so let’s scale that up:

final Random randomGenerator = new Random();
final List<Rational> list = new ArrayList<>();
for (int i=0; i<4000; ++i) {
    list.add(Rational.valueOf(4000000 + randomGenerator.nextInt(5000),
            4000000 + randomGenerator.nextInt(20000)));
}
return list;

That took 77 seconds! More than 4 times as long as for half the amount of data. The resulting number has over 26000 digits. Obviously, this scales way worse than linear.

An Explanation

By now it was pretty clear what was happening: The ever so slightly not-1 values were causing an “explosion” in the denominator after all. When two denominators are coprime, i.e. their greatest common divisor is 1, the length of the denominators just adds up. The effect also happens when the gcd is very small, such as 2 or 3. This can happen quite a lot with huge numbers in a sufficiently large range. So when things go bad for your input data, the length of the denominator just keeps growing linearly with the number of input values, making each successive addition slower and slower. Your rationals just exploded.

Conclusion

After this, it became apparent that using rationals was not a great idea after all. You should be very careful when doing series of additions with them. Ironically, we were throwing away all the precision anyways before presenting the number to a user. There’s no way for anyone to grok a 26000 digit number anyways, especially if the result is basically 4000.xx. I learned my lesson and buried the dream of perfect arithmetic. I’m now using fixed point arithmetic instead.

The migration path for Java applets

Java applets have been a deprecated technology for a while. It has become increasingly difficult to run Java applets in modern browsers. Browser vendors are phasing out support for browser plugins based on the Netscape Plugin API (NPAPI) such as the Java plugin, which is required to run applets in the browser. Microsoft Edge and Google Chrome already have stopped supporting NPAPI plugins, Mozilla Firefox will stop supporting it at the end of 2016. This effectively means that Java applets will be dead by the end of the year.

However, it does not necessarily mean that Java applet based projects and code bases, which can’t be easily rewritten to use other technologies such as HTML5, have to become useless. Oracle recommends the migration of Java applets to Java Web Start applications. This is a viable option if the application is not required to be run embedded within a web page.

To convert an applet to a standalone Web Start application you put the applet’s content into a frame and call the code of the former applet’s init() and start() from the main() method of the main class.

Java Web Start applications are launched via the Java Network Launching Protocol (JNLP). This involves the deployment of an XML file on the web server with a “.jnlp” file extension and content type “application/x-java-jnlp-file”. This file can be linked on a web page and looks like this:

<?xml version="1.0" encoding="UTF-8"?>
<jnlp spec="1.0+" codebase="http://example.org/demo/" href="demoproject.jnlp">
 <information>
  <title>Webstart Demo Project</title>
  <vendor>Softwareschneiderei GmbH</vendor>
  <homepage>http://www.softwareschneiderei.de</homepage>
  <offline-allowed/>
 </information>
 <resources>
  <j2se version="1.7+" href="http://java.sun.com/products/autodl/j2se"/>
  <jar href="demo-project.jar" main="true"/>
  <jar href="additional.jar"/>
 </resources>
 <application-desc name="My Project" main-class="com.schneide.demo.WebStartMain">
 </application-desc>
 <security>
  <all-permissions/>
 </security>
 <update check="always"/>
</jnlp>

The JNLP file describes among other things the required dependencies such as the JAR files in the resources block, the main class and the security permissions.

The JAR files must be placed relative to the URL of the “codebase” attribute. If the application requires all permissions like in the example above, all JAR files listed in the resources block must be signed with a certificate.

deployJava.js

The JNLP file can be linked directly in a web page and the Web Start application will be launched if Java is installed on the client operating system. Additionally, Oracle provides a JavaScript API called deployJava.js, which can be used to detect whether the required version of Java is installed on the client system and redirect the user to Oracle’s Java download page if not. It can even create an all-in-one launch button with a custom icon:

<script src="https://www.java.com/js/deployJava.js"></script>
<script>
  deployJava.launchButtonPNG = 'http://example.org/demo/launch.png';
  deployJava.createWebStartLaunchButton('http://example.org/demo/demoproject.jnlp', '1.7.0');
</script>

Conclusion

The Java applet technology has now reached its “end of life”, but valuable applet-based projects can be saved with relatively little effort by converting them to Web Start applications.

Explicit types – and when to use them

Many modern programming languages offer a way declare variables without an explicit type if the type can be inferred, either dynamically or statically. Many also allow for variables to be explicitly defined with a type. For example, Scala and C# let you omit the explicit variable type via the var keyword, but both also allow defining variables with explicit types. I’m coming from the C++ world, where “auto” is available for this purpose since the relatively recent C++11. However, people are still debating whether you should actually use it.

Pros

Herb Sutter popularised the almost-always-auto style. He advocates that using more type inference is good because it is roughly equivalent to programming against interfaces instead of implementations. He says that “Overcommitting to explicit types makes code less generic and more interdependent, and therefore more brittle and limited.” However, he also mentions that you might sometimes want to use explicit types.

Now what exactly is overcommiting here? When is the right time to use explicit types?

Cons

Opponents to implicit typing, many of them experienced veterans, often state that they want the actual type visible in the source code. They don’t want to rely on type inference being right. They want the code to explicitly state what’s going on.

At first, I figured that was just conservatism in the face of a new “scary” feature that they did not fully understand. After all, IDEs can usually infer the type on-the-fly and you can hover on a variable to let it show you the type.

For C++, the function signature is a natural boundary where you often insert explicit types, unless you want to commit to the compile time and physical dependency cost that comes with templates. Other languages, such as Groovy, do not have this trade-off and let you skip explicit types almost everywhere. After working with Groovy/Grails for a while, where the dominant style seems to be to omit types whereever possible, it dawned on me that the opponents of implicit typing have a point. Not only does the IDE often fail to show me the inferred type (even though it still works way more often than I would have anticipated), but I also found it harder to follow and modify code that did not mention explicit types. Seemingly contrary to Herb Sutter’s argument, that code felt more brittle than I had liked.

Middle-ground

As usual, the truth seems to be somewhere in the middle. I propose the following rule for when to use explicit types:

  • Explicit typing for domain-types
  • Implicit typing everywhere else

Code using types from the problem domain should be as specific as possible. There’s no need for it to be generic – it’s actually counter-productive, as otherwise the code model would be inconsistent with model of the problem domain. This is also the most important aspect to grok when reading code, so it should be explicit. The type is as important as the action on it.

On the other hand, for pure-fabrication types that do not respresent a concept in the domain, the action is important, while the type is merely a means to achieve this action. Typically, most of the elements from a language’s standard library fall into this category. All your containers, iterators, callables. Their types are merely implementation details: an associative container could be an array, or a hash-map or a tree structure. Exchanging it rarely changes the meaning of the code in the problem domain – it just changes its performance characteristics.

Containers will occasionally contain domain-types in their type. What do you do about those? I think they belong in the “everywhere else” catergory, but you should be take extra care to name the contained type when working with it – for example when declaring the variable of the for-each loop on it, or when inserting something into it. This way, the “collection of domain-type” aspect will become clear, but the specific container implementation will stay implicit – like it should.

What do you think? Is this a useful proposition for your code?

What’s your time, database?

Time is a difficult subject. Especially time zones and daylight saving time. Adding layers makes things worse. Ask your database.

Time is a difficult subject. Especially time zones and daylight saving time. Sounds easy? Well, take a look.
Adding layers in software development complicates the issue and every layer has its own view of time. Let’s start with an example: we write a simple application which stores time based data in a SQL database, e.g. Oracle. The table has a column named ‘at’. Since we don’t want to mess around with timezones, we use a column type without timezone information, in Oracle this would be ‘Date’ if we do not need milliseconds and ‘Timestamp’ if we need them. In Java with plain JDBC we can extract it with a call to ‘getTimestamp’:

Date timestamp = resultSet.getTimestamp("at");

The problem is now we have a timestamp in our local timezone. Where is it converted? Oracle itself has two timezone settings: for the database and for the session. We can query them with:

select DBTIMEZONE from dual;

and

select SESSIONTIMEZONE from dual;

First Oracle uses the time zone set in the session, then the database one. The results from those queries are interesting though: some return a named timezone like ‘Europe/Berlin’, the other return an offset ‘+01:00’. Here a first subtle detail is important: the named timezone uses the offset and the daylight saving time from the respective timezone, the offset setting only uses the offset and no daylight saving. So ‘+01:00’ would just add 1 hour to UTC regardless of the date.
In our example changing these two settings does not change our time conversion. The timezone settings are for another column type: timestamp with (local) timezone.
Going up one layer the JDBC API reveals an interesting tidbit:

Timestamp getTimestamp(int columnIndex)
throws SQLException

Retrieves the value of the designated column in the current row of this ResultSet object as a java.sql.Timestamp object in the Java programming language.

Sounds about right, but wait there’s another method:

Timestamp getTimestamp(int columnIndex,
Calendar cal)
throws SQLException


Retrieves the value of the designated column in the current row of this ResultSet object as a java.sql.Timestamp object in the Java programming language. This method uses the given calendar to construct an appropriate millisecond value for the timestamp if the underlying database does not store timezone information.

Just as in Oracle we can use a named timezone or an offset:

Date timestamp = resultSet.getTimestamp("at", Calendar.getInstance(TimeZone.getTimeZone("GMT+1:00")));

This way we have control over what and how the time is extracted from the database. The next time you work with time based information take a close look. And if you work with Java use Joda Time.

VB.NET for Java Developers – Updated Cheat Sheet

The BASIC programming language (originally invented at Dartmouth College in 1964) and Microsoft share a long history together. Microsoft basically started their business with the licensing of their BASIC interpreter (Altair BASIC), initially developed by Paul Allan and Bill Gates. Various dialects of Microsoft’s BASIC implementation were installed in the ROMs of many home computers like the Apple II (Applesoft BASIC) or the Commodore 64 (Commodore BASIC) during the 1970s and 1980s. A whole generation of programmers discovered their interest for computer programming through BASIC before moving on to greater knowledge.

BASIC was also shipped with Microsoft’s successful disk operating system (MS-DOS) for the IBM PC and compatibles. Early versions were BASICA and GW-BASIC. Original BASIC code was based on line numbers and typically lots of GOTO statements, resulting in what was often referred to as “spaghetti code”. Starting with MS-DOS 5.0 GW-BASIC was replaced by QBasic (a stripped down version of Microsoft QuickBasic). It was backwards compatible to GW-BASIC and introduced structured programming. Line numbers and GOTOs were no longer necessary.

When Windows became popular Microsoft introduced Visual Basic, which included a form designer for easy creation of GUI applications. They even released one version of Visual Basic for DOS, which allowed the creation of GUI-like textual user interfaces.

Visual Basic.NET

The current generation of Microsoft’s Basic is Visual Basic.NET. It’s the .NET based successor to Visual Basic 6.0, which is nowadays known as “Visual Basic Classic”.

Feature-wise VB.NET is mostly equivalent to C#, including full support for object-oriented programming, interfaces, generics, lambdas, operator overloading, custom value types, extension methods, LINQ and access to the full functionality of the .NET framework. The differences are mostly at the syntax level. It has almost nothing in common with the original BASIC anymore.

Updated Cheat Sheet for Java developers

A couple of years ago we published a VB.NET cheat sheet for Java developers on this blog. The cheat sheet uses Java as the reference language, because today Java is a lingua franca that is understood by most contemporary programmers. Now we present an updated version of this cheat sheet, which takes into account recent developments like Java 8:

Declaration-site and use-site variance explained

A common question posed by programming novices who have their first encounters with parametrized types (“generics” in Java and C#) is “Why can’t I use a List<Apple> as a List<Fruit>?” (given that Apple is a subclass of Fruit) Their reasoning usually goes like this: “An apple is a fruit, so a basket of apples is a fruit basket, right?”

Here’s another, similar, example:

Milk is a dairy product, but is a bottle of milk a dairy product bottle? Try putting a Cheddar cheese wheel into the milk bottle (without melting or shredding the cheese!). It’s obviously not that simple.

Let’s assume for a moment that it was possible to use a List<Apple> as a List<Fruit>. Then the following code would be legal, given that Orange is a subclass of Fruit as well:

List<Apple> apples = new ArrayList<>();
List<Fruit> fruits = apples;
fruits.add(new Orange());

// what's an orange doing here?!
Apple apple = apples.get(0);

This short code example demonstrates why it doesn’t make sense to treat a List<Apple> as a List<Fruit>. That’s why generic types in Java and C# don’t allow this kind of assignment by default. This behaviour is called invariance.

Variance of generic types

There are, however, other cases of generic types where assignments like this actually could make sense. For example, using an Iterable<Apple> as an Iterable<Fruit> is a reasonable wish. The opposite direction within the inheritance hierarchy of the type parameter is thinkable as well, e.g. using a Comparable<Fruit> as a Comparable<Apple>.

So what’s the difference between these generic types: List<T>, Iterable<T>, Comparable<T>? The difference is the “flow” direction of objects of type T in their interface:

  1. If a generic interface has only methods that return objects of type T, but don’t consume objects of type T, then assignment from a variable of Type<B> to a variable of Type<A> can make sense. This is called covariance. Examples are: Iterable<T>, Iterator<T>, Supplier<T>inheritance
  2. If a generic interface has only methods that consume objects of type T, but don’t return objects of type T, then assignment from a variable of Type<A> to a variable of Type<B> can make sense. This is called contravariance. Examples are: Comparable<T>, Consumer<T>
  3. If a generic interface has both methods that return and methods that consume objects of type T then it should be invariant. Examples are: List<T>, Set<T>

As mentioned before, neither Java nor C# allow covariance or contravariance for generic types by default. They’re invariant by default. But there are ways and means in both languages to achieve co- and contravariance.

Declaration-site variance

In C# you can use the in and out keywords on a type parameter to indicate variance:

interface IProducer<out T> // Covariant
{
    T produce();
}

interface IConsumer<in T> // Contravariant
{
    void consume(T t);
}

IProducer<B> producerOfB = /*...*/;
IProducer<A> producerOfA = producerOfB;  // now legal
// producerOfB = producerOfA;  // still illegal

IConsumer<A> consumerOfA = /*...*/;
IConsumer<B> consumerOfB = consumerOfA;  // now legal
// consumerOfA = consumerOfB;  // still illegal

This annotation style is called declaration-site variance, because the type parameter is annotated where the generic type is declared.

Use-site variance

In Java you can express co- and contravariance with wildcards like <? extends A> and <? super B>.

Producer<B> producerOfB = /*...*/;
Producer<? extends A> producerOfA = producerOfB; // legal
A a = producerOfA.produce();
// producerOfB = producerOfA; // still illegal

Consumer<A> consumerOfA = /*...*/;
Consumer<? super B> consumerOfB = consumerOfA; // legal
consumerOfB.consume(new B());
// consumerOfA = consumerOfB; // still illegal

This is called use-site variance, because the annotation is not placed where the type is declared, but where the type is used.

Arrays

The variance behaviour of Java and C# arrays is different from the variance behaviour of their generics. Arrays are covariant, not invariant, even though a T[] has the same problem as a List<T> would have if it was covariant:

Apple[] apples = new Apple[10];
Fruit[] fruits = apples;
fruits[0] = new Orange();
Apple apple = apples[0];

Unfortunately, this code compiles in both languages. However, it throws an exception at runtime (ArrayStoreException or ArrayTypeMismatchException, respectively) in line 3.

How I find the source of bugs

You know the situation: a user calls or emails you to tell you your program has a problem. Here I illustrate how I find the source of the problem

You know the situation: a user calls or emails you to tell you your program has a problem. When you are lucky he lists some steps he believe he did to reproduce the behaviour. When you are really lucky those steps are the right ones.
In some cases you even got a stacktrace on the logs. High fives all around. You follow the steps the problem shows and you get the exact position in the code where things get wrong. Now is a great time to write a test which executes the steps and shows the bug. If the bug isn’t data dependent you normally can nail it with your test. If it is dependent on the data in the production system you have to find the minimal set of data constraints which causes the problem. The test fails, fixing it should make it green and fix the problem. Done.
But there are cases where the problem is caused not in the last action but sometime before. If the data does not reflect that the problem is buried in layers between like caches, in memory structures or the particular state the system is in.
Here knowledge of the frameworks used or the system in question helps you to trace back the flow of the state and data coming to the position of the stack trace.
Sometimes the steps do not reproduce the behaviour. But most of the time the steps are an indicator for how to reproduce the problem. The stack trace should give you enough information. If it doesn’t, take a look in your log. If this also does not show enough info to find the steps you should improve your log around the position of the strack trace. Wait for the next instance or try your own luck and then you should have enough information to find the real problem.
But what if you have no stack trace? No position to start your hunt? No steps to reproduce? Just a message like: after some days I got an empty transmission happening every minute. After some days. No stack trace. No user actions. Just a log message that says: starting transmission. No error. No further info.
You got nothing. Almost. You got a message with three bits of info: transmission, every minute and empty.
I start with transmission. Where does the system transmit data. Good for the architecture but bad for tracing the transmission is decoupled from the rest of the system by using a message bus. Next.
Every minute. How does the system normally start recurring processes? By quartz, a scheduler for Java. Looking at the configuration of the live system no process is nearly triggered every minute. There must be another place. Searching the code and the log another message indicates a running process: a watchdog. This watchdog puts a message on the bus if it detects a problem. Which is then send by the transmission process. Bingo. But why is it empty?
Now the knowledge about the facilities the system uses comes into play: UMTS. Sometimes the transmission rate is so low that the connection does not transfer any packages. The receiving side records a transmission but gets no data.
Most of the time the problem can be found in your own code but all code has bugs. If you assume after looking at your code that the frameworks you use have a bug. Search the bug database of the framework hopefully it is found there and already fixed.

When UTF8 != UTF8

Not all encoding problems are problems with different encodings

Problem

Recently I encountered a problem with umlauts in file names. I had to read names from a directory and find and update the appropriate entry in the database. So if I had a file named hund.pdf (Hund is German for dog) I had to find the corresponding record in the database and attach the file. Almost all files went smooth but the ones with umlauts failed all.

Certainly an encoding problem I thought. So I converted the string to UTF-8 before querying. Again the query returned an empty result set. So I read up on the various configuration options for JDBC, Oracle and Active Record (it is a JRuby on Rails based web app). I tried them all starting with nls_language and ending with temporary setting the locale. No luck.

Querying the database with a hard coded string containing umlauts worked. Both strings even printed on the console looked identically.

So last but not least I compared the string from the file name with a hard coded one: they weren’t equal. Looking at the bytes a strange character combination was revealed \204\136. What’s that? UTF8 calls this a combining diaeresis. What’s that? In UTF8 you can encode umlauts with their corresponding characters or use a combination of the character without an umlaut and the combining diaeresis. So ‘ä’ becomes ‘a\204\136’.

Solution

The solution is to normalize the string. In (J)Ruby you can achieve this in the following way:

string = string.mb_chars.normalize.to_s

And in Java this would be:

string = Normalizer.normalize(string, Normalizer.Form.NFKC)

Ruby uses NFKC (or kc for short) as a default and suggests this for databases and validations.

Lesson learned: So the next time you encounter encoding problems look twice it might be in the right encoding but with the wrong bytes.

Finally: return considered harmful

No wonder nobody wants to write explicit return statements anymore. They are more dangerous than you might think.

Ok, calm down already – I’m not going to take your return statement away. It’s a nice little statement that gets rarer and rarer,  mostly because many modern languages allow for implicit return values, e.g. in Scala, everything is an expression and the last expression of a method is its return value – except when it isn’t. You dont need to write an explicit return statement anymore, so our laziness takes over and we omit it.

And I’m not argueing that a finally block is a bad thing – quite the contrary. Even in the age of try-with-resources and autoclose closures, a well-crafted finally block is a beautiful piece of code at its right place.

But put the two together and you’ve got a recipe for desaster, at least in Java (try it in your language of choice with care). Let’s have a look at code:

public void doSomething() {
    try {
        throw new Error("drama!");
    } finally {
        // dispose resources here
    }
}

Ok, I could have spared you the drama of an Error and just thrown a RuntimeException (or a declared and checked Exception), but it’ll soon illustrate the effect all the better.

First, the code does exactly what it should: if you call the method, you’ll get to catch an Error and all resources that were used inside the method are cleaned up right before you catch it. And since the method has no return value, you don’t miss out there.

But what if I want to give one of those endangered return statements a new home and insert it into the finally block?

public void doSomething() {
    try {
        throw new Error("drama!");
    } finally {
        // dispose resources here
        return;
    }
}

Not much has changed. I’m still not missing any return value and the Error still gets thrown. The resources are cleaned up quite as thorough as before, but something important has changed: You won’t ever see the Error. You won’t catch it because it gets eaten by that return statement at the end of the finally block.

So in short: return statements are hungry little beasts that will eat your Throwables if you corral them inside a finally block.

No wonder nobody wants to have them in their code if they behave like that.

Oh, and rest assured that you will be warned: All modern IDEs will point you to the inevitable desaster waiting to happen, if only with a compiler warning.

But where do Throwables go when they got eaten? Good question. They don’t show up on any UncaughtExceptionHandler, they don’t even stay in memory. Probably, they just are digested, never to be seen again.

If you don’t regard return statements as a little more dangerous now, you probably also raise switch-statements for fun.

Recap of the Schneide Dev Brunch 2014-06-22

If you couldn’t attend the Schneide Dev Brunch at 22nd 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 smaller this time, but we held the last brunch only three weeks ago. We had bright sunny weather and used our roof garden, but hurdled in the shadows. 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:

Student again – from full employee to university

One of our attendees worked as a full-time software developer in the recent years and decided to study again. He told us about the practical challenges of an employee turned student:

  • The bureaucracy at universities is highly developed and not on your side. It takes days to accomplish the tiniest step towards matriculation.
  • To listen again. In the developer world, two hours of highly concentrated programming is satisfying, but two hours of concentrated listening to somebody who tells the important stuff only once is very hard. You are allowed to doze off (just like in big meetings), but it won’t do you no good.
  • Higher-level mathematics. Suddenly, all that stuff about fourier transformation and matrices is very important again.
  • Running on a lower gear. It seems like heaven to replace a 40h work week with a 20h study week, but the irregular pace (one day no lectures, one day lectures around the clock, etc.) will take its toll.
  • Self-organization. Good developers are of course self-organized and know what to do: work on the most important issues in your issue tracker/todo list. But university will not write issues for you and you are the one to fill the todo list. We joked that a “master’s student JIRA” would actually be a good idea.

It was a very entertaining talk and we digressed lots of times. Let’s have a look at some artifacts we came across during our discussion:

  • There seems to be a growing influence from military concepts on management. On book was specifically mentioned: “Turn the ship around” by David Marquet.
  • “Bad work, good work and great work”. It’s a marketing video, but contains a message nonetheless. One practical advice is to not include “bad work knowledge” in your curriculum vitae, even if you have expertise in it. This minimizes the risk that your next job will contain a lot of “bad work” again.

The current state of JavaFX

Last year, JavaFX was aggressively marketed by Oracle as the next big thing in desktop UI. The claims and promises seem to finally be fulfilled. The combination of Java 8 and the latest JavaFX is especially joy-bringing. The JavaFX core is included in Java 8 and brings a lot of little but essential improvements. You can layout and design your graphical interfaces with a WYSIWYG editor and store it in XML-based layout files. These layouts are loaded, combined with custom logic and bound to custom data sources. The styling is based on a slightly outdated CSS dialect, but very powerful and done right in comparison to styling in past toolkit like Swing or SWT.

The best thing about JavaFX is that much less GUI code is needed for more pleasant user experiences. The toolkit feels alive and the details tell that the developers care and eat their own dogfood. Integration in the Eclipse IDE is enhanced by the e(fx)clipse project.

Our attendee has hands-on experience with Swing, SWT/JFace and JavaFX. If pressed to choose the technology for a new project, he would choose JavaFX anytime now.

Efficiency killers

We also traded tales about the most efficient efficiency killers in software development that we actually observed or endured:

  • Taking away notebooks and desktop computers and replacing them with zero clients – for developers that really need their multi-cores and gigabytes.
  • Restricting every employee to one (and only one!) computer. If you happen to choose a notebook, you probably don’t need that extra monitor, do you?
  • Installing a “privilege management” software. Basically, this software works like a firewall against user inputs. You want to install a new printer driver? It will be cheaper and faster to carve your text in stone slabs.
  • Fragmenting the company networks. This is actually a very good idea. You can have a wild-west style network for developers and a “privilege managed” one for management. It gets complicated when you need to cross the canyons everytime to get work done. Just imagine that your repository is behind a firewall and you need a clearance every time you want to commit/push.

Introduction to warfare

The last main topic was an overview of a self-study on warfare. And because the typical software developer won’t move whole armies around, it concentrated more on the principles and strategies of “common” warfare, which includes everyday conflicts as well as campaigns for a certain goal (e.g. establishing a technology). Three books serve as stepping stones:

  • “The art of war” by Sun Tzu. The ancient classic book about warfare. There are probably a dozen different translations of the original chinese text, but they will only serve as a starter. This book alone will probably don’t give you deep insights, but you will come back to it often when you venture deeper into the mindset of warriors and generals.
  • “Die Kunst der List” by Harro von Senger. This german book describes the political and rhetorical battle moves that are often used in everyday life. These so-called strategems can be identified and parried if you know about them. Most of us can react to some strategems by learnt lessons, but it certainly helps to be keen about the rest of them, too.
  • “The 33 Strategies of War” by Robert Greene. This book doesn’t mess around. It is part of the “immoral series” of books about topics that don’t get discussed in this clarity often. You’ll learn much about strategies, their actual application in history (not only on the battlefield, but on movie sets, offices and political stages) and how to counter them. The book has a lot of content and many ideas and concepts to think about. And it contains an exhaustive list of literature to continue reading.

Is TDD dead?

We continued our discussion about the debate around David Heinemeier Hansson’s frontal attack on the hype around Test Driven Development. There were some new insights and an improved understanding about the manyfold contents of the hangout discussions.

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.