/k-nucleotide

nucleotide DNA sequence freq command line tool - fork of the programming language "benchmark" game

Primary LanguageJava

the k-nucleotide frequency counter

this is an implementation that's intended to meet the requirements of the programming language "benchmark" game's k-nucleotide task

  • read a FASTA format file from standard input
  • extract the third sequence
  • count certain nucleotide sequences
  • write results to standard output

modifications

  • architectural improvements: static methods are replaced with classes
  • input is read in larger buffers
  • parallel processing of input

results

  • running at the bash prompt using the builtin time
  • on an i5-3570 on ubuntu 16.04
  • the median "user" runtime of 21 runs
  • modified: real 0m2.937s
  • original: real 0m3.970s
  • 35% faster (or a 26% reduction in processing time)

i'm not running on either the official Q6600 cpu or python script

  • i don't have access to that cpu (it's from 2007)
  • the official script requires extensive customization and that isn't repeatable

data

modified original
2.869s 3.736s
2.895s 3.767s
2.895s 3.779s
2.896s 3.780s
2.905s 3.786s
2.913s 3.788s
2.917s 3.789s
2.926s 3.806s
2.931s 3.808s
2.934s 3.809s
2.937s 3.970s
2.954s 3.973s
2.963s 3.990s
3.014s 3.999s
3.087s 4.010s
3.101s 4.024s
3.137s 4.039s
3.156s 4.040s
3.170s 4.056s
3.174s 4.064s
3.175s 4.088s

running

	 alias java="$java11/bin/java -Xms2G -Xmx2G"
	 cp=$(mvn -q dependency:build-classpath -Dmdep.outputFile=/dev/fd/1)
	 java -cp target/classes:$cp fasta 1000 > input.txt
	 java -cp target/classes:$cp knucleotide < input.txt | diff - output.txt 
	 java -cp target/classes:$cp fasta 25000000 > t1
	 time java -cp target/classes:$cp knucleotide < t1
	 { for ii in {1..12}; do time java -cp target/classes:$cp knucleotide < t1 > /dev/null; sleep 10; done; } 2> x2

	 # compare vs orig
	 rm -Rf v1 v2 w1 w2
	 git checkout orig   && mvn clean compile && mv target/classes v1
         git checkout master && mvn clean compile && mv target/classes v2
         for ii in {1..21}; do for jj in 1 2; \
	     do { time java -cp v$jj:$cp knucleotide < t1 > /dev/null; } 2>&1 | tee -a w$jj; \
	     sleep 10; done; done

other versions of java should work as well

the "benchmark" game

the following verbage is included in the header block of the source code:

the "benchmark" game is terrible for a number of reasons, including:

  • the test harness is difficult to configure and use, making the barrier to optimization abnormally high
  • the tests are not representative of common programming tasks
  • there's no attempt to account for JIT warmup, and many of the tasks are too short to ever warm up
  • the maintainers are opinionated in terms of what code they'll allow, effectively choosing the winners
  • doesn't appear to allow for jvm options to be included
  • the test cpu is from 2007 and is not necessarily representative of current cpus this is not a meaningful benchmark in any way and the use of the term should be removed from the game

for that matter, it's not really a game either. and the included code is not of good quality and shouldn't be used as a starting point to solve real problems. due to these flaws, it is intentionally not linked from this document

in particular, it's worth highlighting the flaws in one of the key arguments that the proponents and "maintainers" of this game make. as justification for not properly accounting for startup, the "maintainers" write:

JVM start-up, JIT, OSR… are quickly effective and typical cold / warmed-up comparison at most of these workloads will show miniscule difference

it is plausible that this statement is true for (some of) the current implementations. but because of this policy, it favors implementations that compile quickly, at the expense of better code that would ultimately be easier to maintain and perform better

further work

  • profile the code
  • look at JIT timing and tweak code to encourge compiling
  • look at the uniqueness of the hash function
  • alternative hashmaps could also be looked at (koloboke would be good for java 8)
  • the c# code uses unsafe, which might be useful here too
    • a hashmap impl that uses unsafe to store the key and value at the same location might have value beyond this demo
  • break up processing depending on fragment length
    • short fragments should use unity hash
  • move executor service into the class and look at startup cost

it's not allowed by the game spec, but for real usage it would be interesting to try a suffix (or other) tree (or trie)