Hash read performance (perl,ruby,python,node.js)

After having read the chapter "How Hashes Scale From One To One Million Elements" from the book "Ruby Under A Microscope" (This post does not dispense the reading of the respective chapter), I decided to play around with the subject and make some tests with other languages and do a small analysis of the performance of each. The chosen languages ​​were Perl, Ruby, Python and Javascript (node.js).

The tests focused on measuring the time in ms when retrieving an element from a hash with N elements 10.000 times and were based on tests that were performed on the book.

The tests were run on an Amazon EC2 server instance (free tier) with the following characteristics:

• Ubuntu Server 12.04 LTS
• Instance type micro
• Intel(R) Xeon(R) CPU E5430 @ 2.66GHz
• 604.364 KB of memory
• 64-bit platform

Test description

Programs have been implemented for each of the languages ​​to be tested and they are similar as long as possible.The implementation passed by the creation of hashes with size equals to powers of 2, ranging from 1 to 20.

For each of the hashes created, are made 10.000 gets of the value for a key (key=target_index), and measuring the time in milliseconds.

The ​​measured values are placed in an output file for later to be consumed by a program that will generate the graphics.

Comparing Ruby Versions

From the graphs we can see greater improvements from ruby 1.8 to ruby 1.9 so 1.9 is the the way to go.

Time taken to retrieve 10.000 values (ms)

Comparing Perl Versions

Perl is a language with some years and performance has been stable at least since version 5.8, the results show it.Yet I hoped there were more commitment from the community in trying to optimize these values​​.

Time taken to retrieve 10.000 values (ms)

Comparing Python Versions

The versions of python show few variations and show some stability between versions. However python 3.2.3 shows a slight degradation in performance.
I may also say that it's performance is quite interesting.

Time taken to retrieve 10.000 values (ms)

Comparing Languages

Represented in the graph below are the tests for all languages ​​and respective versions.

Time taken to retrieve 10.000 values (ms)

Python was the winner for the interpreted languages. node.js has a great performance however the library used in node.js is not enough accurate to give us reliable values.

You can easily do the tests in your environment using my scripts, the source code used in this tests can be found on Github. I've used rvm, perlbrew and pythonbrew to switch between versions, you can do the same if you want. Nevertheless, you can use your installed versions.

Run the tests:

$ ./experiment1.rb

$ ./experiment1.pl

$ ./experiment1.py

The execution of these scripts will create an output file in the form "values.#{lang}-#{version}" (ex: values.perl-5.8.8) for each script.

To generate the graph just run the ruby script (requires gem googlecharts):

$ ./chart.rb

This script will output the link to the googlechart image.

In the near future I might do the same but for hash writes and that will be more interesting.

Count the number of 1's

I've participated in a Quiz where i had to implement a function that counts the number of 1's required to reach a positive integer passed as a parameter.

Example:

countOfOnes (12) = 5
1 - one 1
3
4
5
6
7
8
9
10 - two 1's
11 - four 1's
12 - five 1's

Since countOfOnes (1) = 1, they have requested to find the next number in which the parameter is equal to the return value of countOfOnes ( countOfOnes(n) = n ).

At first glance I've implemented a perl one-liner that returns the number of 1's for an input number. Here it is:

$ perl -e '$sum += () = /1/g for 1..shift; print "NumberOfOnes=$sum\n"' 111

NumberOfOnes=36

However, this solution was inefficient due to the high number of invocations needed to find the solution to the quiz.

So, analyzing the evolution of the mathematical calculation of the function numOfOnes, I outlined the following recursive algorithm:

# NumOfOnes
sub num_of_ones{
  my $n = shift;

  return 0 if $n < 1;
  return 1 if $n <= 9;

  my @a = split('',$n);

  my $len = length($n);
  my $sum = 0;
  my $delta = 0;

  if($a[0] > 1){
    $delta += 10**($len-1);
  }else{
    $delta += substr($n,1) + 1;
  }

   $sum += $delta + $a[0]*num_of_ones(9x($len-1))+ num_of_ones(substr($n,1));
   return $sum;
}

Since, recursive functions were used, which were invoked repeatedly with the same parameters, I used the Memoize module, which makes caching for functions with the same parameters.

Although the previous function is more efficient for calculating the numberOfOnes just for a single number, it is not when you want to go all the way incrementing to find the next number that satisfies the requested condition. Once we have the numOfOnes for the previous number, we only need to count the numOfOnes that exists in the current number and increment numOfOnes of the previous number.

The following perl on-liner is a better approach to achieve that

perl -e 'while(1){$sum += () = ++$i =~ /1/g; print "Found:$i\n"  if $i == $sum;}'

Found:1
Found:199981
Found:199982
Found:199983
Found:199984
Found:199985
Found:199986
Found:199987
Found:199988
Found:199989
Found:199990
Found:200000
Found:200001

The number after the 1 that satisfies the condition countOfOnes(n) = n is 199981


The source code is here.