Certainly an oxymoronic subject, and not without justification- any decent high-level language developer will leverage existing libraries that have been designed for optimal performance (at least among the majority of use cases). Optimization and high performance in these environments often focuses on architectural and engineering disciplines, not a science of algorithm optimization and memory management. Certainly, any developer worth their weight should understand the basic concepts in computer science, but you’re not likely to find a vast array of efficient search algorithms implemented in Javascript or Ruby. Development platforms (and in turn, high-level languages) are built with the best possible performance in mind to enable developers to create and build without focusing on plumbing code. This does not, however, limit a language or environment’s ability to provide efficient methods of data management, nor should it preclude a developer from leveraging the most efficient (and safest, and sanest) solution possible.
I’ll use Perl as an example testbed, largely because Perl’s array primitives do not contain any sort of search of find method- if you want to know if a is in b[], you’re gonna have to go index spelunking (and yes, I’m submitting that phrase to Webster). The use of a simple loop and matching on a sentinel is easy enough to implement, and in a small data set, looping through the entirety of an array likely won’t be too expensive. Alternatively, converting the array to a hashmap and checking the existence of the key is an acceptable solution– but is it really worth it? We’ll take a look at both the cost of searching through both types of data structures, and the time needed to build each list:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#! /usr/bin/perl use strict; use Time::HiRes qw(gettimeofday tv_interval); my $start = 1; my $ctr = 1; my $increment = 10; my $sets = 8; print("*** Testing search speed ***\n\n"); printf("%-30s%-15s%s\n", "", "Linear Search", "Hashmap Search"); for (my $i = $start; $ctr <= $sets; $i *= $increment) { searcher($i); ++$ctr; } $ctr = 1; print("\n\n*** Testing data structure speed ***\n\n"); printf("%-30s%-15s%s\n", "", "Linear Search", "Hashmap Search"); for (my $j = $start; $ctr <= $sets; $j *= $increment) { builder($j); ++$ctr; } sub searcher { my $max = shift; my $match = $max; my @linear_array = (); my %hashmap = (); my $t_linear_elapsed; my $t_hashmap_elapsed; for (1 .. $max) { $linear_array[$_] = $_; $hashmap{$_} = 1; } my $t_linear_start = [gettimeofday]; for (1 .. $max) { if ($linear_array[$_] == $match) { $t_linear_elapsed = tv_interval($t_linear_start); last; } } my $t_hashmap_start = [gettimeofday]; if (exists $hashmap{$match}) { $t_hashmap_elapsed = tv_interval($t_hashmap_start); } printf("%-30s%-15s%s\n", "Testing $max items...", $t_linear_elapsed, $t_hashmap_elapsed); } sub builder { my $size = shift; my @linear_array = (); my %hashmap = (); my $t_linear_start = [gettimeofday]; for (1 .. $size) { push(@linear_array, $_); } my $t_linear_elapsed = tv_interval($t_linear_start); my $t_hashmap_start = [gettimeofday]; for (1 .. $size) { $hashmap{$_} = 1; } my $t_hashmap_elapsed = tv_interval($t_hashmap_start); printf("%-30s%-15s%s\n", "Testing $size items...", $t_linear_elapsed, $t_hashmap_elapsed); } |
Which results in the following:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
*** Testing search speed *** Linear Search Hashmap Search Testing 1 items... 7e-06 4e-06 Testing 10 items... 4e-06 2e-06 Testing 100 items... 1.4e-05 2e-06 Testing 1000 items... 0.000117 2e-06 Testing 10000 items... 0.001071 2e-06 Testing 100000 items... 0.006427 3e-06 Testing 1000000 items... 0.065786 4e-06 Testing 10000000 items... 0.679214 5e-06 *** Testing data structure speed *** Linear Search Hashmap Search Testing 1 items... 1.1e-05 7e-06 Testing 10 items... 6e-06 1e-05 Testing 100 items... 1.9e-05 4.9e-05 Testing 1000 items... 7.6e-05 2.763121 Testing 10000 items... 0.001069 0.006338 Testing 100000 items... 0.010422 0.064446 Testing 1000000 items... 0.11407 0.603997 Testing 10000000 items... 0.793241 7.436346 |
It doesn’t take a rocket surgeon to understand how the first test scales. Increasing the search range of a linear function by an order of magnitude increases run time… by an order of magnitude. Shocker. Meanwhile, Perl’s exists() function runs in near-constant time (and I say near with a nod to DVK). With regard to data structure construction, we see another story- O(n) time for both structure forms, though the hashmap’s slope is greater. This is a function of the complexity of how Perl manages memory structures. Essentially, the choice between linear and hash searches is dictated by use case- large data sets that are created, then searched sparingly, will perform better overall using a linear search, since the time to build the hashmap may outweigh the benefits gained from a constant search time; existing large data sets, or those that already live in the form of a hash map, should clearly be searched via hash key checking methods.
We can see the same results of linear vs. hashmap search comparison in another high-level language- embeded Lua:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
local linear = {} local hash = {} local match = 10000000 local linear_start local linear_finish local hash_start local hash_finish for i = 1,match do linear[i] = i hash[i] = true end ngx.update_time() linear_start = ngx.now() -- linear search for i = 1,#hash do if (linear[i] == match) then ngx.update_time() linear_finish = ngx.now() end end ngx.update_time() local hash_start = ngx.now() -- hashmap search if (hash[match] == true) then ngx.update_time() hash_finish = ngx.now() end ngx.say("Linear search took: " .. linear_finish - linear_start) ngx.say("Hash search took: " .. hash_finish - hash_start) |
|
1 2 3 |
root@fw01-west:~# curl cryptobells.com/search Linear search took: 0.019999980926514 Hash search took: 0 |
The Nginx Lua API doesn’t provide high-resolution timer checking that we can get in Perl, so this test case is limited to a single example (plus the Lua GC is apparently not strong enough to handle millions of items; see my post to the Openresty mailing list). Still, we can clearly see that implementing a hash search is much more efficient as the data set grows, and in a web environment (picture a shared memory zone holding millions of IPs in a behavioral analysis algorithm) that receives thousands of concurrent requests, squeezing out those extra 19 milliseconds of performance can make a significant difference.