I’m back after some time spent on hard working, overtiming, doubleshifting and all that since my daytime project was heading for a rough landing. On the up side it gave me a lot to think and write about. Here’s the first topic – queue implementations and thread sleeps.

First of all, what motivated this – quite often (too often) I see a piece of code that looks like this:

Where the queue is shared among producers and consumers. The problem with this code is that if you run it, it’s going to spin. If the queue is more often empty then not (and it most likely is if you don’t have enormous amounts of data flowing through it). A very frequent modification of this ‘pattern’ is one with Thread.Yield() or Thread.Sleep(0) (they’re equivalend) after the while loop.

I used to think that it’s not all that bad, the Yield would give back the scheduled time without spinning much, the waste would be only on context switching, but it wouldn’t be that CPU consuming. Wrong! It does perform slightly better under overall CPU heavy load, but in ‘idle’ mode, it still consumes a whole one CPU core (if there is one consumer).

Another variation of this is something like Thread.Sleep(1) or Thread.Sleep(5). While it helps in idle mode, it has a couple of problems. It still does a lot of context switching completely unnecessairly and it also delays your processing (the bigger the sleep value, the larger the delay, the less context switching)

So how can we do better? I used to use some form of Monitor.Wait and Monitor.Pulse/PulseAll  was a good solution, and while it works fine it’s usually a bit difficult to get completely right and the consequences of not getting it right are dire. If you miss one Pulse or mishandle some exception, you can stop processing or wait while there are messages in queue, or a whole bunch of other unwanted stuff can happen.

Happily, .NET 4.0 introduced a BlockingQueue. This code:

can completely replace what we’ve had above (minus the cancellation, we’ll get there in a moment).

The foreach loop will block until there are elements in the collection and will consume them in a nice thread safe manner. When a producer is done adding, they can call collection.CompleteAdding() and the loop will end for all consumers.

The BlockingCollection contains a bunch of static methods that allow different behaviors dealing with mulltiple collections at one (AddToAny/TakeFromAny) that also can take cancellation tokens and bail out nicely if you decide to quit processing. One word of caution – it’s not guaranteed to behave as if there were any priorities – if you have two blocking collections and you do TakeFromAny, you’ll most likely receive elements from the first one (if there are any) and then from the second one, but it’s not a guaranteed behavior (at least I have not found it documented anywhere). In .NET 4 and 4.5 ILSpy can tell us that it will always behave this way, but in 5.0+ – who knows.

One last thing. This behavior brings me to mind another cool library for .NET – reactive extensions (parts of it – some interfaces – are actually a part of the framework). In short it’s a way of treating your collections (or any deta sources) as sort of ‘data available event producers’ (and more). It’s pretty robust, and it plays nicely with linq. Check it out here: http://msdn.microsoft.com/en-us/data/gg577609.aspx.

 

Some time ago when working on some performance critical serialization code for a C# project, I was looking deeply into all flavors of available serialization benchmarks. One thing that struck me at the time was that there weren’t that many of them. The most comprehensive I’ve found was this one: http://www.servicestack.net/benchmarks/NorthwindDatabaseRowsSerialization.100000-times.2010-08-17.html Published by service stack so maybe a little biased, but pretty neat nonetheless.

The test published were pretty in line with what I have observed – protobuf was a clear winner, but if you didn’t want to (couldn’t) use open source, DataContractSerializer was best available to you.

After some more testing, I started finding some discrepancies between this report and my tests and they we’re pretty big – it seemed that DataContractSerializer was better than reported, and the whole order was sometimes shuffled . It all boiled down to two major differences that I’ll explain here

 

Data Contract Serializer performance

In the quoted tests, DataContractSerializer was almost 7 times slower than protobuf. That’s a lot. In my tests it was 3 times slower. Big difference, huh ? When I ran the tests on my own machine (the thing I love about people at servicestack.net is that they published on GIT the source to their tests so that you could reproduce it at home) I found that DataContractSerializer was 7 times slower. So obviously, there had to be a difference in the way we used it! And indeed there was, when I added my version it was 2,8 times slower than protobuf running on the same test set. Here’s the difference:

Original:

My version:

See the difference ?

Sure, it’s binary, you can’t always use it, but in most cases it will do, and it’s way faster. I also noticed, that the payload size is about 1/3 more than JsonDataContractSerializer, which is actually pretty good, so if you’re worried by bandwidth usage, it’s an additional plus. Here are the results of running the Northwind test data with just one additional serialization option (binary one) on my machine:

Serializer Larger than best Serialization Deserialization Slower than best
MS DataContractSerializer 5,89x 10,24x 5,38x 7,24x
MS DataContractSerializerBinary 4x 3,01x 2,75x 2,85x
MS JsonDataContractSerializer 2,22x 8,07x 9,59x 9,01x
MS BinaryFormatter 6,44x 10,35x 6,23x 7,81x
ProtoBuf.net 1x 1x 1x 1x
NewtonSoft.Json 2,22x 2,83x 3,00x 2,94x
ServiceStack Json 2,11x 3,43x 2,48x 2,84x
ServiceStack TypeSerializer 1,67x 2,44x 2,05x 2,19x

 

Having this difference aside, the results were more consistent with my tests, but still there were big differences in some cases, which leads us to second important point

 

It’s all about data

There is nothing that will be best for all cases (even protobuf), so you should carefully pick your use case. In my tests, the data was larger, and usually more complex than in Northwind data set used for benchmarking by servicestack.net. Even if you look at their results, the smaller data set the bigger the difference – for RegionDto which has only one int and one string, the DataContractSerializer is 14 times slower (10 times slower on my machine, binary XML for DataContractSerializer is 3,71 slower).

So, does the DataContractSerializer perform better (especially in binary version) if larger objects are involved? It does indeed.

I created a EmployeeComplexDto class that inherits from EmployeeDto and adds some data as follows:

The object being serialized  consisted of not more than 10 Orders, 10 Customers and 10 Friends (for each test the same amount and the same data), and here’s what I got serializing and deserializing this 100 000 times:

Serializer Payload size Larger than best Serialization Deserialization Total Avg per iteration Slower than best
MS DataContractSerializer 1155 1,88x 6407245 6123807 12531052 125,3105 4,11x
MS DataContractSerializerBinary 920 1,50x 2380570 3452640 5833210 58,3321 1,91x
MS JsonDataContractSerializer 865 1,41x 7386162 14391807 21777969 217,7797 7,14x
MS BinaryFormatter 1449 2,36x 9734509 7949369 17683878 176,8388 5,80x
ProtoBuf.net 613 1x 1099788 1948251 3048039 30,4804 1x
NewtonSoft.Json 844 1,38x 2844681 4272574 7117255 71,1726 2,34x
ServiceStack Json 844 1,38x 4904168 5747964 10652132 106,5213 3,49x
ServiceStack TypeSerializer 753 1,23x 3055495 4606597 7662092 76,6209 2,51x

So – are you really ‘stuck’ with DataContractSerializer, or is it quite good ? The answer is of course – it depends. Surely, whenever you can, use the Binary Writer as it is way faster, but even if you do, whether it’s a best choice or not can be answered only with a specific use case in mind – think about what data will you be serializing, how often, etc.

As always with reasoning about performance, best option is to test with your data, in close to real scenarios and (preferably) on similar hardware as the application is going to run in production. The closer you get to this, the more accurate your tests will be.

 

The other day I was watching .NET cryptography tutorials on pluralsight (http://pluralsight.com/training/Courses/TableOfContents/cryptography-introduction-dotnet) and one thing struck me – there were some performance tests for SHA hash algorithms, the results of which were couter-intuitive. Namely – the SHA512 was faster than SHA256. I’m not an expert in cryptography, but i know a thing or two how SHA works and I could see nothing that could justify those results. So I did some testing

The result of 1000 hashings of 10 KB file on my PC:

SHA 256 – 202 ms.

SHA 512 – 955 ms.

 

Now that’s not what I’ve seen in the video ! I ran the ILSpy (http://ilspy.net/) on the libraries  and a thing that immediately stands out as a difference between SHA256 and SHA512 (note: I was using System.Security.Cryptography.SHA256Managed, there is another flavor of SHA256 and I’ll talk about that later) is that where SHA256 uses int, SHA512 uses ulong.

Aha! I quickly recompiled everything as x64 and as expected the results were mighty different:

SHA 256 – 201 ms.

SHA 512 – 130 ms.

Now it makes sense. I guess historically framework designers thought that by the time SHA512 will be a standard, all compilations will be x64 bit so it made sense to speed it up for those kinds of builds.

 

One other interesting thing is that there are two (at least) mechanisms for SHA computation in .NET. The *Managed one (SHA1Managed, SHA512Managed,etc.) is older and it is not certified to be FIPS 140-2 compliant (which basically means it’s potentialy less secure and you definitely shouldn’t use it if you’re writing software for government/military or public safety use). The other option is to use CryptoServiceProviders (SHA512CryptoServiceProvider, SHA256CryptoServiceProvider, etc.). It’s altogether a better option because compliance aside, those algorithms are faster as they use native windows libraries instead of managed implementations (The only drawback is that you need framework 3.5+).

Here are all the results for different providers and different systems.

compilation SHA256Managed SHA512Managed SHA256CSP SHA512CSP
x86 202 ms. 955 ms. 150 ms. 256 ms.
x64 201 ms. 130 ms. 114 ms. 73 ms.

 

So, the bottom line – use CryptoServiceProvider wherever possible and get ready to move on to 64 bit compilation if you need that extra security and/or extra performance (there is about a gazilion reasons to do it anyway)

 

 

About a year ago we had some internal coding challenge in the company, in which I decided to take part. The goal was simple enough – we were given a huge file (couple of GB) in a specific format where some IDs were put on a per-row basis along with other attributes. The goal was to read off of standard input the ID and find the associated attributes (or return some error i think when the ID did not exist). The entries were sorted according to the ID .

The language was not specified, you could use any. I used C#.

With data being more or less random it was very hard to do better than just binary search, though I’ve tried various algorithms (interpolation search with binary search cutoff was in some cases a little better) but ended up with a straight binary search. I had however a small caching algorithm that was building a map of pointers to the original file so that the initial binary search would be performed in-memory rather than seeking in  the heavy file. The cache was only ensuring it was sparse enough to ensure it’s size was below 512K. This was because the test procedure involved running the program multiple times on single-item inputs rather than once on multi-item input, so I judged that loading/saving may contribute too much if the cache was large).

The benchmark for me was simply the amount of reads of the disk until the answer could be given and I managed to keep it at about 13 which compared with raw binary search was a bit better (16 without cache).

Imagine my surprise when after all tests were ran, my program took twice as much as the best one !

Of course I started analyzing why did this happen and there were two very interesting conclusions:

1. Loading and Saving

HDD disks nowadays have about 32MB of cache. One thing that I noticed was that when I ran my program twice on the same input, it returned instantly. Just because the data being accessed on the disk was already in the cache and could be returned in no time. I assumed the same (to perhaps an even higher degree) would happen to my cache being saved and loaded each time the process started.

I was wrong. Loading and especially saving 512KB of data takes time. A lot of time if you do that frequently. In our test cases, the program was ran couple of hundreds of times with different inputs. That means a couple of hundred of loads and possibly as many saves (there not always were changes in the cache, but thanks to some re-balancing there often where).

After removing the cache and reverting to the raw binary search, the program was still 25% slower than the winning one, still having one major disadvantage, but no longer having the cache.

2.Process startup time

Now we come to the main point that interested me in this story – .NET process startup time.

In native code, the binary EXE file is just executed. The binary format (PE) of the EXE defines where the code starts (where the bootstrap code starts) so that the OS can just go ahead and execute this. In .NET world however, all we have is a managed assembly. When you execute a managed EXE, it jumps to a initialization function in mscoree.dll (If I’m not mistaken, it’s a Windows dll, not a framework dll, so it will tell you so even if you don’t have the framework installed at all). There it is decided which CLR version should be initialized (1.0/2.0/4.0) and only after this initialization CLR JITs and executes your managed code. This initialization has to take time. But how much of it ?

First – some baseline tests:

Most basic program, not doing anything, just main function that exits immediately. Executed 500 times using a batch script on my PC.

.NET version DEBUG RELEASE
2.0 39,08 s 39,55 s
4.0 37,55 s 36,08 s
4.5 36,25 s 35,51 s

Note here that 4.0 and 4.5 are not really different CLR types – it’s just framework and compiler.

Having this baseline I tried different things to speed up the startup – first changing the build type to x86/x64 instead of any cpu. Result – nothing.  The numbers didn’t differ by more than a single second (and sometimes in the wrong direction)

Next – removing all the referenced assemblies. Result – the same – no change.

After some more unsuccessful attempts of trying various optimization and compilation options which yielded nothing I’ve found the only thing that in my tests has made any difference. NGEN.

Pre-generating the native image (thus removing the need for JIT compiling) speeded up the startup time by about 10% (the best in class 4.5 compilation reached 32,63 s). All other attempts for optimization didn’t provide signifficant results.

For comparison I wrote a similar program in C++ (main function, return immediately), and used the same test procedure. The result – 26,85 s.

A bonus lesson learned (at least for me) was that for any competition before you submit your program one should check the impact of the test procedure on ones program. It may just make all the difference.

 

Stability testing is important, but often overlooked. Especially in stable products. We had a saying about one of the products I was working that it had two bugs – one known and one hidden. And that every time you fixed any of them it immediately (and miraculously) returned to a stable state of having two bugs.

After spending about two weeks trying to find and fix one of them, we resolved to find and fix both. Surely enough there were some signs of the other – hidden bug – namely the number of handles reported by task manager. After a couple of days it was reaching 15 000. That’s a lot of handles event for a server application. Of course the worst thing was that after weekend of idleness, the handle count didn’t go down (unless you restarted the application and then it started growing again from nominal ~150).

In situations like these WinDbg is an invaluable ally and we quickly found out that the handles are mostly to a stopped threads and are not released because a finalizer thread is stuck.

Not only stuck but stuck with a very peculiar stacktrace:

Wait for single object? No wonder it’s frozen. But what is it waiting on ?  One thing worth noticing is the last line of the abbreviated stacktrace here which seems to be pointing at some COM object problem.

Some digging inside revealed the following piece of code:

I really don’t like WMI management objects, I find them hard to work with and the API somewhat cryptic, but sometimes there is no way around it. This particular code what being executed as a part of startup configuration from the main thread which then proceeded to execute some main program timer loop. Now the thing about the management objects is that they sometime have (or use something that has) destructors which are executed by the finalizer thread.

Say your main method looks like this:

I see a lot of methods like this (especially in software that is about 5-8 years old ;) If your readConfiguration() method is using something that will be accessing COM object in a destructor – you’re in trouble (your Finalizer thread will show the same stacktrace as the one in the beginning of this post).

Now why is that: the whole issue boils down to the annotation above the Main method – [STAThread]. Your main thread while creating the COM object will associate it with its own Single Threaded Apartment. Because of this, when finalizer thread will want to do something with this COM object, it won’t be able to do this directly, but will have to do it through the thread that created this COM object – your main thread. Your main thread however will be busy doing other things and not willing to proxy to the COM object (even if you do the Thread.sleep). The end result will be your finalizer thread frozen waiting, your handle count growing and eventually a crash of the application.

How to alleviate this problem – there are multiple ways to avoid it. Easiest fix is to just remove [STAThread], provided you don’t need it for other COM objects. Other is to execute your COM object creating code in another thread that is MTA. I chose to avoid using WMI at all – we’ve found that the reading of service start mode was completely unnecessary and there only for legacy reasons.

One interesting thing I noticed is that if you call GC.WaitForPendingFinalizers() in main thread, it will indeed wait, but also will release the finalizer thread from its waitOne by interacting with the COM on its behalf.

The other day I was watching a new series of lectures about Least significant digit Radix sort given by Robert Sedgewick and Kevin Wayne on Coursera (https://www.coursera.org/course/algs4partII) and it got me thinking – why don’t I use it anywhere ?

I got so comfy with Java’s mergesort and Comparable<T> that I never thought on optimizing that even in some performance critical code. So i though i should at least check what the performance impact can be.

LSD Radix sort is only useful in cases where you have a reasonable length of the keys on which you are sorting, so for my tests I assumed long as THE key data type. Reasoning behind was the following datatype:

since timestamp (Date object) can be expressed as long, and it’s perfectly reasonable to sort by date, it will do.

There are two additional things I had to define to enable more general sorting:

An interface that allows for extracting the sort key from object (and thus allowing for sorting various object by various keys – an equivalent of Comparator) and implementation of that for my data type.

So now for the sort itself:

So how this works:

We start by extracting the keys to a separate array (to avoid extracting them for every pass). It’s an optimization step, but it’s worth to do it, since calling the extractor method that many times will be expensive (but of course, there is a memory trade-off). Then, for each double octet (16 bits) starting from least significant ones, we do a key-index counting sort on extracted keys also moving the objects themselves into an auxiliary array. The result of each pass is an array sorted by that double byte. Because the sort is stable, we can start from least significant and move ‘up’.

The method is nor overly complicated, there are a couple of subtleties though:

lines 20-21 and 34-35 – the XOR with most significant bit of the most significant byte is required in order to correctly sort the negative numbers (negating the sign bit)

lines 40-46 – exchanging the auxiliary array with initial array (or just two aux arrays in case of keys) is needed in order to avoid copying all elements from aux array which is typically done in one-pass key-index sort.

Also note here, that thanks to the fact we have an even number of passes (4), we use the input array as an auxiliary array in the last pass, so we end up with sorted elements in original array and there is no need to copy elements from aux array to the original array.

So, is this any good ? Here’s results:

Size Comparable LSD Radix
10 0 ms. 10 ms.
100 1 ms. 9 ms.
1_000 3 ms. 6 ms.
10_000 37 ms. 10 ms.
100_000 178 ms. 65 ms.
1_000_000 466 ms. 179 ms.
10_000_000 8882 ms. 2219 ms.

For small number of elements it’s definitely not worth it, but that was expected. Above certain threshold though it definitely makes sense – it’s faster than system sort, and since Java uses mergesort for objects anyway, it doesn’t have that much bigger memory requirements than system sorting (the two aux key arrays, but in performance critical code if you want to sacrifice some purity for performance it too can be avoided).

There is one low-hanging optimization that can double the performance for large arrays – if you can limit your key size to a smaller number of bytes, you can get away with less passes. For example I tested with the Date converted to milliseconds from start of unix epoch which is long datatype, but afterwords did some tests with the key calculated by making the number of milliseconds relative to January 1-st 2000 (since I knew my data set couldn’t contain dates prior to that one) and lowered resolution to seconds which allowed me to fit it in 4 byte int.

It not always can be done, but as with many optimizations – a lot depends on inherent properties of your data.

Everyone (ok, nearly everyone or this wouldn’t happen) knows that if you have a multithreaded application and different threads are accessing shared resources (and some of them do writes), you have to synchronize the access somehow.

Microsoft introduced a neat set of Concurrent Collections in the framework to help with that, but before ConcurrentDictionary there were plain old Dictionary. Some time ago I came across a piece of software that was crashing due to lack of proper synchronization (unfortunately this still happens a lot) and it got me thinking, what is the worst that could happen. So i started experimenting with multiple threads and a Dictionary to see in how many ways can it break. What i found surprised me. Outside of Duplicate Key exception and key not found exception which one may argue are not entirely tied to lack of proper synchronization there are two that stood out.

First one is rather trivial (it’s actually the exception I’ve observed in the aforementioned piece of software, so no surprise there):

Collection is being resized, and we’re still trying to do some operations on it.

The second one is more interesting. At some point my small testing program just didn’t end. I looked at the task manager and this is what I’ve seen:

Inline image 1

25% CPU utilization – most likely one thread going crazy. I connected through WinDBG and here’s some things I’ve seen:

So there is one offending thread – let’s see what it’s doing:

So it seems it’s stuck on inserting – actually inside framework Dictionary class – spinning!

Let’s find this dictionary and see if it’s corrupted:

This is my dictionary, it was declared as Dictionary<long,int>. There is four of them, but that’s because the program was running in a loop creating dictionaries and trying to break them. Remaining three just have not yet been garbage collected as can be observed below

Let’s see if that indeed is the case:

And surely that’s the only one with any gc root at all.

Before we look inside, a word about the structure of Dictionary – there are two important structures inside -

  • int[] buckets – it holds the index of the entries table that contains the first Entry for the hashCode that maps to that bucket
  • Entry[] entries – it contains all the entries in a linked-list fashion (Entry class has a next field pointing to the next Entry)

So the way this works is that if you put object A, a hashCode is calculated for it, then a bucket index is selected by calculating hashCode % buckets.length and the int in the buckets table for that index is pointing at the first entry in that ‘bucket’ that is contained in the entries table. If there is none, yours is the first. If there are some, you iterate the whole chain, and insert after the last one, updating the ‘next’ pointer of the previously last element.

Knowing that, we can look at the structure of my Dictionary:

Ok – just 10 elements inside the Dictionary, let’s see what the Entries look like:

 

For brevity I include only two relevant entries (actually only one is relevant). Entry number six – the next entry is – number seven (so far so good). Entry number seven – the next is … number seven ! Aha! That’s really bad. Concurent inserting (and deleting) without any synchronization has corrupted the Dictionary so that in the Entries linklist one of the entries is pointing at itself!

I would imagine Dictionary code for inserting would look something like this:

With such a corrupted structure this Insertion would then fall into infinite loop spinning on next.next.next… (which is what I could observe)

If you know any other way this could go wrong, send me an email or leave a comment. I’m sure there has to be some other ill behavior resulting from lack of proper synchronization.

Save early, save often. Sounds almost like a gospel, and having experienced various software crashes I usually make sure that I am saving often and making backups and so on. The wordpress blog editor is a little different though. Being used to the fact that in a browser CTRL+S saves the HTML document of the page rather than anything else I didn’t use it (Actually in wordpress blog post editor CRTL+S behaves as you would expect it to – saves draft).

So after writing for an hour while working on previous post and jumping between Eclipse and chrome to report on test results I clicked ‘Distraction Free Writing mode’ which basically is a fullscreen mode. Instead of turning on the fullscreen mode, the editor blinked and the edited text disappeared. CRTL+Z didn’t work, there was nothing left from the post in the page source. A brief look into the database showed that there is nothing there for this post. I was doomed – an hour of work gone.

Then I thought – sure, it disappeared, but it has to be somewhere in process memory still (some cache, not yet cleared). So I turned on the WinDbg, connected to the chrome process (chrome runs the tabs in separate processes, and it has a task manager which allows you to see which process corresponds to which tab). Thankfully I remembered some parts of what I was writing so I searched for “ArrayList implementation”:

0:007>s -a 0 L?80000000 ”ArrayList implementation”

Search for ascii string (-a) in addresses starting from o for 80000000 bytes (L signifies length) matching  ”ArrayList implementation”. And surely enough I got lots of results (~20 of them).

All that was left to do was to trace back to the beginning of the text (“ArrayList implementation” was somewhere in the middle) and dump that memory:

0:007> da 08bdbd10 L40000

0a53d418 “I’ve always thought that Java is”
0a53d438 ” in the wrong by not allowing ge”
0a53d458 “neric collections of primitive t”

I actually managed to recover all of the text thus saving myself an hour of work and 5 tons of frustration. After that I’ve googled on how to turn the auto-save and revisions.

BTW. If you know an easier way to do this – drop me a line, I’ll update the post to include the easiest method.

 

EDIT 1:

Jack Z suggested T-Search which is really a cheating engine for games (one that allows you to freeze you health, ammo or whatever) – It’s got a nice UI and would probably be easier to use and faster than using the WinDbg. It’s got a memory browser with a ASCII search function.

 

I’ve always thought that Java is in the wrong by not allowing generic collections of primitive types. I’ve experienced in the past some situations where boxing and unboxing was the reason of a bottleneck in a performance critical code and always felt when working with C# that for example Dictionary<int,int> is very useful and gives that extra edge with performance So today I’ve done some experiments:

I declared ArrayList<Integer> on which I performed 100 000 inserts followed by removing all elements one-by-one (always removing the first element):

  • 6 ms. for inserts (includes amortized array resizing)
  • 3790 ms. for removes

Oddly enough I found that the removals do not cause the shrinking of the array. Canonical implementations resize by a factor of two up whenever the space runs out, but also shrink the underlying array by a factor of two if it’s 3/4 empty
I checked the Java source code and indeed, there is no shrinking of the array with removals (also the increase is not by a factor of 2 but 3)

But, back to the original thought
Here’s the code i used for my resizable list of primitive integer values:

It uses the same System.arraycopy method to move elements around and Arrays.copyOf for growing as the ArrayList implementation

And the results?

  • 3 ms. for inserts
  • 3117 ms. for removes

Clearly the cost is dominated by remove and in particular by shifting all elements by one ‘left’ which each removal (no surprise there). The shrinking of the array doesn’t help since the move is made only for elements up to current size regardless of the actual array size (it actually adds a little)
So, to make the test more about arraylist of primitive types rather than about why I should never remove the first element from an arraylist and use some other structure instead, I modified the test to always remove the last element, thus making shifting of the elements unnecessary.I also increased the number of elements put to the list to 10 000 000 since it was running much faster now. The result startled me a little:

  • ArrayList add: 2096 ms.
  • ArrayList remove: 467 ms.
  • IntList add: 181 ms.
  • IntList remove: 85 ms.

Now that’s a bigger difference (especially for inserts). So I ran the profiler and here’s what I saw (I actually had to copy the ArrayList code to a separate class in order for the visualVM to show the stats):

  • ArrayList add: 461 ms.
  • IntList add: 296 ms.
  • ArrayList remove: 433 ms.
  • IntList remove: 189 ms.

Of course these numbers are ms calibrated to the system and are so-so accurate, but they show the scale. Without boxing taken into account the numbers are significantly different.I actually tested it again with a slightly modified version where the list of integers inserted was pre-generated and generation time was not added to insert time:

  • ArrayList add: 233 ms.
  • IntList add: 77 ms.
  • ArrayList remove: 205 ms.
  • IntList remove: 160 ms.

The differences here can be accounted for by the lack of error checking in the test application.

So again – back to original point – Is the boxing costly ? Yes, very.

This is an example that was shown to me back in the day when I was at the university. I took a great class ‘Anatomy of Java virtual machine’ taught absolutely brilliantly by prof. Grzegorz Czajkowski  (at the time working for SUN but soon after moving to Google) where we got to play with raw java bytecode and write our own (simple) garbage collectors. Quite challenging for a student but a lot of fun nevertheless.

Anyway, here’s a piece of code:

What will be the result of executing it ?

As expected – a lot of console output.

What if we change the value of the integers a bit ?

Will the output change ?

After running this the program terminates instantly with no output!  (By the way, the incrementation  is not necessary, we could simply start with 128)

It’s the only known to me example where the value has such impact on flow control (if you know any other interesting ones, drop me an email).

It’s all got to do with Boxing/Unboxing and a certain specific caching feature of Java. Let’s dissect it a bit. First of all, let’s look at the conditional statement:

i<j || i>j || i==j

remember, those are Integers, not ints i < j and i > j will force auto unboxing so the comparison will happen with unboxed ints. The == equality comparison however will happen for Integer types and will compare the references. That explains why we get no output for 128 – i and j are simply two different Integer objects, so the reference comparison produces false.

Why then if we set the value to 127 (or 10 for example) do we get an infinite loop ? JVM caches the Integers between -128 and 127 and when you use one of those, it uses a cached one instead of creating new Integer object every time. It’s actually a part of JLS (Java Language Specification) – 5.1.7 Boxing Conversion states “If the value p being boxed is truefalse, a byte, a char in the range \u0000 to \u007f, or an int or short number between -128 and 127, then let r1 and r2 be the results of any two boxing conversions of p. It is always the case that r1 == r2.”

Java 1.6 from certain update allows for specifying the upper threshold of the cached range – by using -XX:AutoBoxCacheMax=<size> JVM option

Some use this example as an argument that you should always use Integer.valueOf() instead of autoboxing. I think you just need to be careful and aware of such behaviors.

EDIT: Check out this blog post: http://martykopka.blogspot.com/2010/07/all-about-java-integer-cache.html It’s explaining how the Integer caching has changed through different versions of Java