GetHashCode() Is it that important ?

Introduction

The Idea for this blog entry came up after a pair code review session.
I’ve noticed the following method (from class that holds picture coordinates):

public override int GetHashCode()
{
    return X.GetHashCode() + Y.GetHashCode(); // Algo. 1
}

At first glance it looked like a fair implementation

I know a few rules of thumb for solid GetHashCode implementation:
•  Hash algorithm must be deterministic (for given input, output must be the same).
•  Equal objects must have the same HashCode.
•  Objects with the same HashCode aren’t necessarily Equals.

This entry overview implementation of GetHashCode.

Preliminary testing

Why it isn’t a solid implementation?
Well let’s test that, the testing will reveal the answers.
The test define image 1024 X 1024 in dimensions, 1M pixels in total.
Our class represents a single pixel on the image,
and override the GetHashCode() method.
Now, let’s calculate the Hash Code for each and every pixel on the image surface.
Values will be compared and summarize according to colliding Hash Code values.

The number of collisions per pixel will indicate the pixel color:
White for collisions free pixels and darker colors correlated
to the “popularity” (see legend) of the Hash Code.

This produces the resulting collisions map for the 1st algorithm result:

 

The results are even worse than expected!
This is mainly due to the fact that .Net implementation of int.GetHashCode()
returns the int value itself!
So,
Pixel(X=50, Y=55).GetHashCode() == 105
Pixel(X=55, Y=50).GetHashCode() == 105
Pixel(X=54, Y=51).GetHashCode() == 105
And so on and on...

Suggested alternative algorithms

Let’s try a slightly better solution:

public override int GetHashCode()
{
    return X.ToString().GetHashCode() 
              + Y.ToString().GetHashCode(); // Algo. 2
}

You can expect using Xor operator between the X and Y
will produce considerably better results:

public override int GetHashCode()
{
    return X.ToString().GetHashCode() 
              ^ Y.ToString().GetHashCode(); // Algo. 3
}

Common solution is to use "Mersenne prime"

public override int GetHashCode()
{
    return X + Y * 31; // Algo 4.
}

Assuming that images dimensions are restricted to 64K (X or Y)
we can create "Perfect Hash"

public override int GetHashCode()
{
    return (X << 16) + Y; // Algo.5
}

Testing output

2nd algorithm result:

3rd algorithm result (Although it looks better, it's even a bit worse):

4th algorithm result (good distribution across the field,

pretty impressive for such simple algorithm):

No use to show the 5th algorithm result, the image is perfect white,

no collisions at all!

Collision effect !

Why the collisions are so important?
Mainly, due to one big reason: Performance !

Let’s try to measure the time it takes to:
Insert / lookup in dictionary (Dictionary<XyPoint, int>) and calculate Hash Code.

This table illustrates the time it takes (1 million POCO items)
for our Algorithms (tested on Intel E8400 machine):

Time in ms.	Algo. 1	Algo. 2	Algo. 3	Algo. 4	Algo. 5
HashCode Calculation	34	280	283	30	31
Dictionary Insert	19,300	2,587	2,758	547	72
Dictionary Lookup	18,614	2,468	2,692	577	98
Total time	37,948	5,335	5,733	1,154	201

Conclusion

Collisions cause huge performance impact.
Even a good Hash algorithm can suffer from a bad implementation
due to incompatibility or misuse.
Although Algo. 1 was one of the fastest Hash calculations,
the overall performance compared to Algo. 5 were about 190 times slower!
This is due to the reason that colliding values are chained,
this requires doing additional search to find the value in the chain.
That’s incredible, small and grey line of code can degrade (or boost) the performance.

Probably next time you’ll override the GetHashCode(),
you’ll spend a little bit more time to find the better solution.

I hope this entry shed some light on the subject and emphasize its importance.

Apprenticeship Program

All professionals around the world need to be trained and software engineers aren't an exception.

Hence, we announce a unique program (and for sure the first in Israel) we are proud to kick off this week: a Software Development Apprenticeship Program.

PicSocut will hire and train apprentices; We will focus (but not limit) on clean code, reading/writing code, clean architecture, BDD, TDD, simple and business oriented designs, tools and best practices. In nutshell, all what you need to become a highly competent software engineer who cares and proud about his profession.

We are looking for couple of candidates to begin the program!

If you feel it's you, please feel free to send us your resume at jobs@picscout.com

Good Luck!

  

Building Lightweight Products

Here is a short talk about how we build lightweight products at PicScout (in Hebrew).
Unfortunately, the video has focused on the speaker, instead of on the slides... so ping us if you wish to receive the slides.

API Best Practices - Introducing PicScout’s API

In the past few months, since we announced our new technological blog, we’ve published many posts regarding our technological point of view. Posts like "Redis as a Messaging Framework", “Javascipt Best Practices” and “Machine Learning Approach to Document Classification” are just a few samples of the posts we’ve published since then.

One thing we came to realize is that you, our devoted readers, can’t really check if what we post about is actually what we do. I mean, what Aran wrote on his post about disposing is really nice, but do we, the PicScout team, really follow those guidelines? Well the answer is clearly yes! But you can’t really know that, can you?

As a result, we’ve decided that it is mandatory for us to publish a post about something our readers can actually put us to the test. In the following few minutes we would like to share with you our point of view about APIs Best Practices and show you how they interpolate in our Web API. Hopefully you’ll accept the challenge to put us to the test.

Let's get started!

There are many ways you can implement your API. Yet, not many of them can ensure you that following them will guarantee a lightweight, flexible and user-friendly API. Following a few simple guidelines, as shown on Uri Lavi’s “API Best Practices” slides here, we’ve implemented our API in a way that ensured us the above features.

Let’s discuss a few of those guidelines.

Is this line secure?

The web is full of data going from one point to another. In PicScout’s case, the data that is transferred from and to our API shouldn’t be visible for anybody besides our trusted partners.

In order to support the secure transfer of our data, we’ve decided that our API should support only secure communication scheme, HTTPS in other words. As a result, each request sent to our API should comply with the following form:

https://api.picscout.com/

What version is this?

As many APIs, PicScout’s API goes through many changes and modification during its life cycle. Framework and endpoints are samples of things that can change during that time. Such changes and modification should be applied without causing third-party tools that use our API to break. As a result, versioning is a one of the crucial features we’ve implemented in our API.

This feature is easily achieved by specifying the API's version as part of the request URI. More specifically, the API version is the first segment of the URI after the base address. For example, the URI for sending requests to our API will look as follows:

https://api.picscout.com/v1/

This feature will allow us in the future to make major changes, if needed, to our API without the fear that any third-party tool that uses our API will break.

“English ******, do you speak it?”

At the end of the day, the data is handled by two machines, the client and the server. Yet one thing any API developer should keep in mind - APIs are for humans!

Keeping that in mind, we’ve decided to keep our API's URI formats as readable as possible. In order to achieve this feature we use basic English grammatical terms such as nouns, verbs and relationships. No more programmers’ favorite method names in the URI.

For example, let’s say you want to get the details of an image that has 12345 as its id. One way we could achieve that is by sending a request as follows:

https://api.picscout.com/v1/getImageDetails?id=12345

This seems to us a bit… well… ugly. As you might have guessed, there is a clear relationship between an image and its id. Furthermore, there is also one between our API and all the images in our storage. Considering this, it is only logical that the request should have the following format:

https://api.picscout.com/v1/images/12345

In translation to English, you want to get access to all our images details but only to the one with 12345 as its id. Simplicity in action.

“Hey! You promised verbs! You cheated!” – “Well allow me to retort”. Another operation we expose through our API is to search for similar images in our storage based on an image URL or its binary data. So in order for you to use that ability all you got to do is to set the URI format in the following manner:

https://api.picscout.com/v1/search?url=<imageURL>

In translation to English, you want to search for images that are similar to the one you provided. Yet again, simplicity in action.

Don’t reinvent the wheel

You might have noticed that I “forgot” to show you an example of how you can search for images based on an image binary data. Well I had to “forget” about it in order to illustrate the following concept. So please, forgive me.

Not all images are stored online, like the ones you have stored on your PC. Thus, no URL can be provided to access them. Exactly for this type of cases, we at PicScout, decided that is mandatory for us to support the search of similar images based on an image binary data.

But wait, we already used the “search” verb to search for images based on URL! Well lucky for us we can always add another endpoint like: 

https://api.picscout.com/v1/search_binary?data=<imageBinaryData>

And there you have it, minor additions create major abilities right? NO! Why on earth would you want to add another endpoint to an operation you already support? And pass binary data as part of the URI?

Luckily for us, there is more than one method we can use to access endpoints. In fact, considering how lucky we are, why not just use those methods and by that make our API much more readable and user-friendly

So to make a long story short, since the operation is the same operation (“search”), we decided that it will be better if what distinguishes between the two requests is the method. For searching an image based on URL we use the GET method. For binary data based search we use the POST method where the binary data itself is passed in body of the request.

As a result, all you have to do in order to use our binary data based search is to attach the image file to the POST request’s body and send it over to:

https://api.picscout.com/v1/search

Why do I need to know all of this?

As you might know, the amount of data that is transferred over the web is enormous. In addition, this amount only keeps getting larger and larger. To put it simple, more cargo means more weight and more weight means more time spent moving it, unless new and improved trucks are constructed. Most of us don’t have control over the trucks construction comity, but we do have control (or at least partial control) over the cargo.

Using that knowledge, one should always try to find more efficient ways to transfer his\her cargo or data in our case. So without further ado, the PicScout team is proud to present one of our API’s major, and the coolest in my opinion, features – The Field Selector!!!

On the client side, the field selector allows you, our trusted partner, to specify exactly which information you want to retrieve. On the server side, which is our Eco-friendly API, it allows us to send back only a relatively small amount of data which can transfer much faster.

“How?” you say? Well that’s really simple; just name the fields you want to include in the response and you’re good to go. For example, let’s say you only want to know where you can buy the image with 12345 as its id. All you have to do is send the following request:

https://api.picscout.com/v1/images/12345?fields=purchaseUrl

In conclusion, following the few simple guidelines we discussed in this post helped us, at PicScout, reaching our goal in creating a simple, readable and flexible API. To support this claim, we implemented 3 client in 3 different languages: Node.JS, Python and C# in our case.

While as exciting as it is to implement the same code in 3 different languages, the interesting part was a tiny rule we agreed on; each implementation shouldn’t take more than 10 minutes. To be fair, it took us around 5 minutes each.

But that’s not such a big deal, considering we know our API from top to bottom. So this is where you, if you’re up for it, step in. We challenge you to implement a client for our API, in any language you’ll like. Same rule applies here, 10 minutes and that’s it! No need to send us your code or anything like that, just share your experience. To those of you that are not interested in the challenge, you’re more than welcome to try out our API’s abilities.

One last thing, before you go playing around with our API. As many other Web APIs, our API supports only request that are sent from known users. In order to identify yourself as one, contact us for key requests and we’ll issue one for you along with our API documentation. 

We hope you enjoyed reading this post and looking forward to adding more exciting new features to our API based on your feedback.

Code Retreat at PicScout

At the end of January we've reserved some time from our busy schedule to conduct a code retreat at PicScout.

For that propose we invited a very special guest, who was visiting Israel as a guest of the Software Craftsmanship community: Corey Haines.

Corey introduced himself to the team and then outlined the code retreat day.

We were supposed to implement a short program, called Conway's Game of Life in continuous series of sessions, each introducing and emphasizing a different idea/angle in the coding craft.

According to Corey, the idea was to perfect our knowledge and coding techniques by concentrated practice. 

Just with the introduction, Corey mentioned very important thing: It is somehow a wrong perception that experienced/mature developers write perfect code. 

Actually their code isn't beautiful (nor perfect), but the difference between the un-experienced and highly experienced developers is that their code will be perfect enough. 

My own take on that is that only when you are an expert, only then you will be able to decide when this enough is enough (there are no rules, just experience and practice)

According to Corey, the purpose of the code retreat (to some degree) is to teach us how to seek a perfect enough code.

After a short introduction the fun began.

We coded in pairs for 45 min. 

At the end of each session we deleted the code and started over from scratch.

And yes, you're not mistaken; We deleted the code.

Somehow, during the history of our profession we learned the unwritten rule: 

Thee shell not delete any code.

Here is again my take on this: Deleting actually makes a lot of sense, since typing code isn't the real problem.

The real problem is reading (and maintaining) our code.

Therefore, the same writing 101 techniques apply when composing code. 

Write, Re-read then Re-read again. If it doesn't make sense Delete it. Start over. 

After deleting the code, we've reflected on what happened during the session. A few questions popped up and Corey provided short answers and directions.

In my opinion, the main idea was to let us to "find out" the right approach instead of providing a solid answer. 

Swapping pairs contributed to the diversity of the solutions. 

Each pair provided a unique solution and a unique approach that revealed different ways of solving a problem.

So what we did?

I. We started by exploring the problem. 

Conway's game of life is a nice problem that cannot be solved in 45 min. 

The first session was just to become familiar with the problem.

Needless to say that almost nobody (except the algorithm's team :) ) produced something coherent enough during this session.

II. Next we touched a sensitive topic, called a "better design". 

You know what it is when you call somebody else and tell him that this isn't how he should build his software (guess what happens a few weeks later when somebody else review your code). 

The idea in this session was that it is quite hard to find what is a "better" design. Therefore we discussed the 4 rules of simple design:

1. Tests Pass

2. Reveals Intent (good names)

3. No Duplication - repeat information and knowledge only once

4. Small (remove redundant, be lean and minimalist)

An interesting remark (with regards to 2) was that WE CAN use verbs to name classes.

Also here, some archaic (and not written rule) taught us that we should use only nouns as the class names. 

Why is that? If it makes sense, if it reveals the content then we shouldn't limit ourselves to those rules.

III. On our third session we touched Test First.

We discussed where from we should start (obviously, from an empty, null or default case). 

We discussed what we want to test or specifically what is the interface/action we would like to reveal during our test (a hint here will be: a tick() action that happens in the Conway's world)

We discussed how our test slowly and gradually reveal the interfaces and the behaviors of our objects (specifically we discussed why a cell needs to have a state)

IV. The fourth session introduced two pairing techniques.

a. A driver (who writes the code) and a navigator (who watches the driver)

b. A driver and a navigator are constantly exchanging their roles (like in a ping pong game)

The problem with the first technique is that it is done in a very statical way: The driver always drives and the navigator almost never touches a keyboard. 

This is obviously quite boring!

The Ping-Pong technique is a better implementation of the Driver/Navigator. There are two forms of a Ping-Pong pairing:

a. Driver: Writes a test. Navigator: Passes the test

b. Driver: Passes a test and writes the next test. Navigator. Passes the test and then writes the next test

Eventually in this session we used a MUTE ping pong style when a driver writes a test and a navigator passes the test.

In addition, Corey introduced the "find the loophole" - the navigator will strive to write a wrong implementation (though in a clean manner) and the driver will strive his best to write the failing tests.

IMO, it was the best session, since there in silence you can really discover the power of the test first and pair programming techniques.

V. In that  session Corey talked about the TDD and Test First techniques. 

Corey explained the difference between the two and how our design should be changed due to the use of the TDD.

In addition, we were introduced with the following constrains on our code:

Contraints:

1. If statements are disallowed (unless these are guard clauses). If statement is a form of procedural programming and usually can be seen as the simplest form of polymorphism.

2. Explicit looping (for, foreach) are disallowed.

3. No primitives across method passing

4. No method with more than 3 LOC (lines of code) 

I assume you guessed correctly, such constrains are really helping in creating more readable and maintainable code. 

VI.

We wrapped the day by asking 3 Questions. 

1. What if anything did you learn?

2. What if anything surprised you?

3. What if anything will you do differently moving forward.

I can definitely say that it was one of the most enjoyable days we had at PicScout and we surely learnt a great deal!

A Practical Guide - From manual to automated QA

Below is a short talk about PicScout's QA practices, which was delivered by Uri Lavi during Agile Practitioners 2012 conference.



Feel free to share with us any additional insights about your own experience in QA automation.

A Week of IL Tech Talks at PicScout

Sharing real life experience for the benefit of Israeli hi-tech community is one of the greatest things we have achieved during the last years.

Ori Lahav’s IL Tech Talks initiative definitely helped in promoting this in our community.
That’s why we happily hosted a full week of those tech talks at PicScout.

We learned a lot: From understanding client side performance, best development practices (here and here), scaling (here and here) to lean practices and management skills.

Amazingly, it appears that “good” things are somehow “reproduced” among the companies. The talks revealed that successful companies are build from the same “forces” in terms of practices and vision. These are exactly the same things we have done and continue to pursue at PicScout.

Unit testing, TDD and Continuous Delivery seems to free business and technology to move safely and together towards the goal. It was quite obvious from Wix’s and Outbrain’s experiences.

For us, being one of the scalable companies in Israel (in terms of billions image recognitions a month), it was very interesting to see others views on scalability.
Specifically (and personally), I would mention here the lecture by Eran Sandler.
Building a truly scalable architecture is hard. Sometimes, it isn’t even necessary till the right conditions are met. Eran’s lecture, introduced small and measured steps to gain scalability without re-writing the code.

Lean techniques (presented skillfully by Elad Sofer) made us to re-enforce our approach of continuous improvement. Building effective communication, seeking and eliminating waste and design for simplicity (yet “useful” products) are skills we all need to embrace and to grow.

Here are some (but not all) of our feedbacks:

Ilya: Once again I have got a validation on how Continuous Delivery and TDD help to create better software - talking about “Building a web infrastructure for 10M users”
Sharon: New ideas on management that will be tested soon ;) - talking about “Team Up”
Merav: Sometimes Agile principles perceived as the new management panacea; Understanding that those principles are here to serve you in a long term is what important - talking about “Lean Software Development”
Arik: I definitely learnt a few new best practices to make our web sites more effective - talking about “Web Performance 101”

We would like to thank all the presenters, who contributed from their own time to present and to share with us their real life experiences!

Database Talk - Unique Identifiers vs. Numeric identities

Wiki

Just to make sure we're all on the same page –

Unique Identifier (which from now on will be referred to as ‘GUID', a.k.a. 'UUID'), is an algorithm-based 32-byte hex string (128 bit integer) which is supposed to generate completely unique values.

I’d like to compare the chances of two identical generated GUIDs to the chance earth will be destroyed by a meteor in the next five minutes.

Now, if that happens – you won’t be here to prove me wrong! J

Here’s one: 5B5D6F63-1FF0-4574-9B77-BD77D716FD66.

It is probably unique and there’s no other like it in the world.

You can read more here - http://en.wikipedia.org/wiki/Globally_Unique_Identifier

Why should I?

With today’s increasing demand for fully-distributed systems, GUID usage is increasing accordingly.

It allows managing two or more disconnected databases which later on need to merge, knowing that each row on desired shared tables is unique.

Here’s a simple example –

Consider a very large company with many branches across the world.

Each branch has local users, and there’s a sync process which merges the entire users list.

The ‘traditional’ way is to maintain a range of numbers for each branch, for example:

-       use a prefix on the username to maintain uniqueness

-       Assign a numeric range for each branch (easier today with SQL 2012's sequences support)

-       Make a combined key of two columns, for example - UserId+BranchId columns

This is a classic sample for using GUID instead – make the UserId column GUID and problem is solved.

Sounds like fun! Any reason why I shouldn’t use it?

Well, yes.

Before you get all excited and change your “int’s” and “bigint’s” to GUIDs, consider the following:

-       GUID column takes 16 bytes, which is double than Bigint (long).

o    This means that index on the column will also take more space

-       Index Fragmentation is an issue and it is most likely to happen.

o    (See more about it on the Tips section below)

-       Not all databases support GUIDs.

o    So, if you migrate to mysql, you'll have to change the datatype to CHAR(32), so it takes even more space as a result

Some Best-Practices Tips:

[Tip #1]

The first, and probably the most important tip, is to avoid using CLUSTERED INDEX on GUID's.

This is because the GUID values are random – a physical sort will cause the table to be re-sorted very frequently and will also result with an excessive I/O consumption.

So do one of the following:

Either create another identity on the table, which also serves as the PRIMARY KEY (also a generic best practice of avoiding 'heap' tables)

OR -

When possible - use the NEWSEQUENTIALID function.

This will create unique GUIDs on a table but will also make sure the new generated GUID is greater than the last. (It is still globally unique as long as the machine has its own MAC address).

Let’s review a quick sample of the differences between the NEWID() function and the NEWSEQUENTIALID default value.

We'll create two tables; each uses one of the techniques:

      -- Creating the tables:    

      IF OBJECT_ID('UsersNewId') IS NULL

      BEGIN

            CREATE TABLE UsersNewId

            (

                  UserId UNIQUEIDENTIFIER PRIMARY KEY NONCLUSTERED DEFAULT NEWID(),

                  UserName VarChar(255)

            )

      END

     

      IF OBJECT_ID('UsersNewSeqId') IS NULL

      BEGIN

            CREATE TABLE UsersNewSeqId

            (

                  UserId UNIQUEIDENTIFIER PRIMARY KEY NONCLUSTERED DEFAULT NEWSEQUENTIALID(),

                  UserName VarChar(255)

            )

      END;

     

      -- Now, let's fill the tables with some data

      -- Note: I'm using SQL2008+ syntax here; On SQL2005 you need to separate the insert statements

      INSERT INTO UsersNewId(UserName) VALUES ('User1'),('User2'),('User3'),('User4'),('User5')

      INSERT INTO UsersNewSeqId(UserName) VALUES ('User1'),('User2'),('User3'),('User4'),('User5')

     

      -- Now, let's see the tables

      SELECT * FROM UsersNewId

      SELECT * FROM UsersNewSeqId

The results:

Note the GUID on the 2^nd table looks the same on first sight, but actually it is not.

These are increasing values that still maintain uniqueness.

This is obviously much better for index fragmentation of any time!

[Tip #2]

Related to the above tip – as a DBA, try to keep the GUID generation on your side!  

Otherwise, if the GUID’s are generated by a different layer in your application (DAL or so), the GUIDs cannot be sequential.  

Besides, try to think as if the GUID’s are actually a new version of your INT identities; you wouldn’t let anyone control the auto-increase now would you?

[Tip #3]

In some cases you may want to consider surrogate keys, which will be used as the foreign key between the tables.

To use the sample at the beginning of this article – each user will have its own GUID, but with an additional “UserInternalId” column (int) which will be the table's primary key.

[Tip #4]

Don’t use GUID if you don’t have to.

When a table needs an ID which does not have to be unique across the enterprise, keep using the regular numeric id.

It takes less space and easier to manage.

Final Words:

GUIDs are great and simple solution to maintain uniqueness across the enterprise.

However, don’t overuse it when not required as it might hurt your databases performances.

This is a very wide subject – hope this in-a-nutshell post helps or at least gives you a good head start.