Sat, 25 Apr 2009

Poor mans dmenu benchmark

I wanted to know how responsive dmenu and awk, sort, uniq are on a 50MB file (625000 entries of 80 1-byte chars each).

generate file:

#!/bin/bash
echo "Creating dummy file of 50MB in size (625000 entries of 80chars)"
echo "Note: this takes about an hour and a half"
entries_per_iteration=1000
for i in `seq 1 625`
do
        echo "Iteration $i of 625 ( $entries_per_iteration each )"
        for j in `seq 1 $entries_per_iteration`
        do
                echo "`date +'%Y-%m-%d %H:%M:%S'` `date +%s`abcdefhijklmno`date +%s | md5sum`" >> ./dummy_history_file
        done
done

measure speed:

echo "Plain awk '{print \$3}':"
time awk '{print $3}' dummy_history_file >/dev/null

echo "awk + sort"
time awk '{print $3}' dummy_history_file | sort >/dev/null
echo "awk + sort + uniq"
time awk '{print $3}' dummy_history_file | sort | uniq >/dev/null

echo "Plain dmenu:"
dmenu < dummy_history_file
echo "awked into dmenu:"
awk '{print $3}' dummy_history_file | dmenu
echo "awk + sort + uniq into dmenu:"
awk '{print $3}' dummy_history_file | sort | uniq | dmenu

Results.
I ran the test twice about an half hour after generating the file, so in the first run, the first awk call may have been affected by a no longer complete Linux block cache.
(I also edited the output format a bit)
Run 1:

Plain awk '{print $3}':
real	0m1.253s
user	0m0.907s
sys	0m0.143s

awk + sort:
real	0m3.696s
user	0m1.887s
sys	0m0.520s

awk + sort + uniq:
real	0m15.768s
user	0m12.233s
sys	0m0.820s

Plain dmenu:
awked into dmenu:
awk + sort + uniq into dmenu:

Run 2

Plain awk '{print $3}':
real	0m1.223s
user	0m0.923s
sys	0m0.107s

awk + sort:
real	0m2.799s
user	0m1.910s
sys	0m0.553s

awk + sort + uniq:
real	0m16.387s
user	0m12.019s
sys	0m0.787s
Plain dmenu:
awked into dmenu:
awk + sort + uniq into dmenu:

Not too bad. It's especially uniq who seems to cause a lot of slowdown. (in this dummy test file, are entries are unique. If there were lots of dupes, the results would probably be different, but I suspect that uniq always needs some time to do its work, dupes or not). The real bottleneck seems to be raw cpu power. Not storage bandwidth at all since Linux caches it. If uncached, I estimate the sequential read would take 1.5 seconds or so. (about 30MB/s on common hard disks)

Once the stuff gets piped into dmenu, there is a little lag but it's reasonably responsive imho.
Test performed on an athlon xp @ 2GHz. 1 GB of memory. There were some other apps running, not a very professional benchmark but you get the idea :)

Comments

You might want to check and see if using "sort -u" instead of "sort | uniq" makes it a little faster. At the very least, it will save you time to fork and do IO over pipes.

Hi, Nice benchmark!
You made me want to test too

Here I'm comparing awk performance against grep and cut.
grep results are astouning!

awk '/1234\.*a/'
real 0m4.385s
user 0m4.184s
sys 0m0.048s

grep -e '1234\.*a'
real 0m0.100s
user 0m0.060s
sys 0m0.020s

Plain awk '{print $3}':
real 0m0.641s
user 0m0.600s
sys 0m0.012s

Plain cut -d ' ' -f 3:
real 0m0.281s
user 0m0.232s
sys 0m0.040s

awk + uniq
real 0m0.979s
user 0m0.792s
sys 0m0.100s

cut + uniq
real 0m0.446s
user 0m0.504s
sys 0m0.060s

So what's your conclusion? If you want to use awk and do regex matching, do it with grep and pipe the output to awk?
for simple "print nth field" awk being twice as slow as cut was to be expected since awk is much more featurefull. But the regex performance is disappointing indeed.

Why do you need to pipe grep output to awk?
awk '//' regexp matching is actually the same as grep

I think that in most cases (at least the ones in uzbl examples) grep and cut can replace awk completely and in all those cases they are faster (that's my conclusion).
sed is also a bit faster in a "s/regexp//" than awk "/regexp/".

I was also wanting to test how does it scale to remove duplicates in my history file before every dmenu launch, and this results have motivated me to start cut|uniq-ing my dmenu.

For what it's worth, your generation script took 28 minutes and 57 seconds on my Core 2 Duo 3GHz, and yielded 2831 unique lines out of the 625000 total. Just for fun, and to highlight just how inefficient the shell is, I translated it to Lua (code below), and it took a mere 11 seconds and yielded a mere 17 unique lines. You might have wanted to use random numbers instead of timestamps if line uniqueness was your goal.

#!/usr/bin/lua require 'md5' print("Creating dummy file of 50MB in size (625000 entries of 80chars)") print("Note: the bash version of this takes about an hour and a half on an old computer") entries_per_iteration = 1000 f = io.open("dummy_history_file", "w") for i = 1,625 do print("Iteration " .. i .. " of 625 ( " .. entries_per_iteration .. " each )") for j = 1,entries_per_iteration do date = os.date("%Y-%m-%d %H:%M:%S") ts = os.date('%s') -- "ts" stands for timestamp md5ts = md5.sumhexa(ts .. "\n") line = date .. " " .. ts .. "abcdefhijklmno" .. md5ts .. " -\n" f:write(line) end end f:close()

(The code requires the Kepler Project's md5 library.)

Well, the generation script definitely was not meant for running fast. 100% uniqueness was never really the goal either. I just needed dummy data, to run my "benchmark" on. If I cared much about execution speed, I wouldn't be forking 4 processes for each line of output ;-)

Out of curiosity I tried running your code, but I can't find the right md5 library. The Arch AUR only has this one: http://luaforge.net/frs/?group_id=155

That's the one; its home page is at http://www.keplerproject.org/md5/ , but when you go to download, it points you to the same LuaForge URL that the AUR uses. I just did a ./configure and make to use it, and didn't even install it as I don't think I'll be using it enough to make it worth it.

I used Lua mostly because it is the fastest scripting language there is, generally. If I were to do it for real, and not just benchmarking purposes, I probably would have used Python or Perl instead, as both have MD5 in their standard library and are included by default in most desktop Linux distros.

After writing the above paragraph, I got the urge to convert it to Python (my scripting language of choice), and amazingly it ended up being faster than Lua, at 7 seconds instead of 11! I'm guessing that something about the MD5 algorithm being in the standard library (and thus probably more optimized) makes Python faster in this case. So while you perhaps like the shell a bit too much, I should have just used my preferred language rather than trying to make it faster with Lua before I knew that Python would have been even better for this purpose.

#!/usr/bin/python # So it will run unchanged in both Python 2 and Python 3 from __future__ import print_function from time import time, strftime from hashlib import md5 print("Creating dummy file of 50MB in size (625000 entries of 80chars)") print("Note: this takes a few seconds") entries_per_iteration = 1000 f = open("dummy_history_file", "w") for i in range(625): print("Iteration {0} of 625 ( {1} each )".format(i, entries_per_iteration)) for j in range(entries_per_iteration): date = strftime("%Y-%m-%d %H:%M:%S") ts = str(int(time())) md5ts = md5((ts + "\n").encode('ascii')).hexdigest() print(date + " " + ts + "abcdefhijklmno" + md5ts + " -", file=f) f.close()

Actually I installed that lualib from AUR but I got an import error.
I don't think it's possible to say "scripting language $foo is always the fastest". Implementations of interpreters have some variations and some similarities, so it depends a lot on the particular use case, imho.

I can't test on my athlon xp right now, but on my laptop (intel Core2 T7200) the python script takes 23seconds,
when I write to /dev/null it's 22 seconds, I guess because there is a bit more cpu time if you leave out my full disk encryption.
(disk i/o itself definitely isn't the bottleneck, it's cpu time)
When I leave out the fopen/fprint/fclose calls, the script ends in 19 seconds.
(fwiw :)

Anyway python is cool, I'm in the process of learning it. It feels more organized and solid then php.


Name:


E-mail:


URL:


Comment:


What is the first name of the guy blogging here?


This comment form is pretty crude. Make sure mandatory fields are entered correctly.
Basic html tags (a,i,b, etc) are allowed, others are sanitized