Results for Enhanced 3n+1 Benchmark for GT.M - 2010-02-28
Computing Platform - System 76 laptop
CPU - Intel Core2 Duo T7500 2.20GHzRAM - 4GB
Disk - Seagate 200GB 7200rpm with SATA interface
OS - Kubuntu 9.10 64-bit Linux kernel 2.6.31-19-generic
File system - jfs
Database - GT.M V5.4-000 64-bit version
Program
In addition to adapting the program to the changes in the benchmark problem, I have also attempted to improve the readability of the program to those who are not GT.M programmers.threeen1eThe resolution of time measured and reported natively by GT.M is one second (higher resolutions are possible by calling a standard external library function).
; Find the maximum number of steps for the 3n+1 problem for all integers through two input integers.
; See http://docs.google.com/View?id=dd5f3337_12fzjpqbc2
; Assumes input format is 3 integers separated by a space with the first integer smaller than the second.
; Third integer is number of threads. No input error checking is done.
; This program is modified to show that the GT.M key-value store can use arbitrary strings for
; both keys and values - instead of numeric subscripts and values to store the numver of steps, each
; subscript and value is spelled out using the strings in the program source line labelled "digits".
;
; K.S. Bhaskar 20100228
;
; No claim of copyright is made with respect to this program.
;
; Variables do not have to be declared before use, but are New'd in subprograms to ensure that they
; do not conflict with names in the caller.
;
; The program uses strings in different languages for each digit in the database. It reads the program
; source at the label digits to get strings (separated by ;) for each language used.
digits ;zero;eins;deux;tres;quattro;пять;ستة;सात;捌;ஒன்பது
Do digitsinit ; Initialize data for conversion between integers and strings
;
; Read and process each line in turn. Since process may be restarting after a crash, any
; data in database is assumed to be as recovered after a crash. After computing and writing
; results from this run, database is cleared for next line of input or next run of the program.
;
; Loop for ever, read a line (quit on end of file), process that line
For Read input Quit:$ZEOF!'$Length(input) Do ; input has entire input line
. Set i=$Piece(input," ",1) ; i - starting number is first piece of input
. Set j=$Piece(input," ",2) ; j - ending number is second piece of input
. Set k=$Piece(input," ",3) ; k - parallel execution streams requested is third piece
. ; Reproduce input on output, formatting numbers
. Write $FNumber(i,",",0)," ",$FNumber(j,",",0)," ",$FNumber(k,",",0)
. ;
. ; Get number of CPUs, calculate number of parallel execution streams, calculate block size
. Open "cpus":(COMMAND="grep processor /proc/cpuinfo|wc -l":READONLY)::"PIPE"
. Use "cpus" Read cpus Use $PRINCIPAL ; Number of CPUS on system is in /proc/cpuinfo
. Close "cpus"
. Set:4*cpus>k k=4*cpus ; At least four execution streams per CPU
. Write " ",k ; Report actual number of execution streams
. Set blk=(j-i+k)\k ; Calculate size of blocks (last block may be smaller)
. ;
. ; Launch jobs. Grab lock l1, atomically increment counter, compute and launch one job for each block of numbers.
. ; Each child job locks l2(pid), decrements the counter and tries to grab lock l1(pid).
. ; When counter is zero, all jobs have started. Parent releases lock l1 and tries to grab lock l2.
. ; When all children have released their l2(pid) locks, they're done and parent can gather & report results.
. Set ^count=0 ; Clear count - may have residual value if restarting from crash
. Lock +l1 ; Set lock for process synchronization
. For s=i:blk:j Do
.. Set c=$Increment(^count) ; Atomic increment of counter in database for process synchronization
.. Set tmp=$Select(s+blk-1>j:j,1:s+blk-1) ; Compute upper limit for numbers for next child Job
.. Set def=$ZTRNLNM("gtm_tmp") Set:'$Length(def) def=$ZTRNLNM("PWD") ; Working directory for Jobbed process
.. Set err=$Text(+0)_"_"_$Job_"_"_s_".mje" ; STDERR for Jobbed process
.. Set out=$Extract(err,1,$Length(err)-1)_"o" ; STDOUT for Jobbed process
.. Set cmd="doblk(s,tmp,i,j):(ERROR="""_err_""":OUTPUT="""_out_""":DEFAULT="""_def_""")" ; Command to Job
.. Job @cmd ; Job child process for next block of numbers
. For Quit:'^count Hang 0.1 ; Wait for processes to start (^count goes to 0 when they do)
. Lock -l1 ; Release lock so processes can run
. Set startat=$HOROLOG ; Get starting time
. Lock +l2 ; Wait for processes to finish
. ;
. ; When parent gets lock l2, child processes have completed and parent gathers and reports results.
. set endat=$HOROLOG ; Get ending time - time between startat and endat is the elapsed time
. ; Calculate duration
. Set duration=(86400*($Piece(endat,",",1)-$Piece(startat,",",1)))+$Piece(endat,",",2)-$Piece(startat,",",2)
. Write " ",$FNumber(^result,",",0) ; Show largest number of steps for the range i through j
. Write " ",$FNumber(^highest,",",0) ; Show the highest number reached during the computation
. Write " ",$FNumber(duration,",",0) ; Show the elapsed time
. Write " ",$FNumber(^updates,",",0) ; Show number of updates
. Write " ",$FNumber(^reads,",",0) ; Show number of reads
. ; If duratation is greater than 0 seconds, display update and read rates
. Write:duration " ",$FNumber(^updates/duration,",",0)," ",$FNumber(^reads/duration,",",0)
. Write !
. Lock -l2 ; Release lock for next run
. Do dbinit ; Initialize database for next run
Quit
;
dbinit ; Entryref dbinit clears database between lines
Kill ^count,^highest,^reads,^result,^step,^updates
Quit
;
digitsinit ; Initialize arrays to convert between strings and integers
New m,x
Set x=$Text(digits)
For m=0:1:9 Set di($Piece(x,";",m+2))=m,ds(m)=$Piece(x,";",m+2)
Quit
;
inttostr(n) ; Convert an integer to a string
New m,s
Set s=ds($Extract(n,1))
For m=2:1:$Length(n) Set s=s_" "_ds($Extract(n,m))
Quit s
;
strtoint(s) ; Convert a string to an integer
New m,n
Set n=di($Piece(s," ",1))
For m=2:1:$Length(s," ") Set n=10*n+di($Piece(s," ",m))
Quit n
;
; This is where Jobbed processes start
doblk(myfirst,mylast,allfirst,alllast)
Set reads=0,updates=0,highest=alllast ; Start with zero reads and zero writes, highest number is at least alllast
Do digitsinit ; Initialize data for conversion between integers and strings
Lock +l2($JOB) ; Get lock l2 that parent will wait on till this Jobbed processes is done
If $Increment(^count,-1) ; Decrement ^count to say this process is alive
Lock +l1($JOB) ; This process will get lock l1($JOB) only parent has released lock on l1
Do dostep(myfirst,mylast) ; Do the block assigned to this process
Do:alllast>mylast dostep(mylast+1,alllast) ; Help with the numbers after this process' block, if there are any
Do:allfirst<myfirst dostep(allfirst,myfirst-1) ; Help with the numbers before this process' block, if there are any
TStart () ; Update global statistics inside a transaction
; The following line unconditionally adds the number of reads & write performed by this process to the
; number of reads & writes performed by all processes, and sets the highest for all processes if the
; highest calculated by this process is greater than that calculated so far for all processes
Set:$Increment(^reads,reads)&$Increment(^updates,updates)&(highest>$Get(^highest)) ^highest=highest
TCommit
Lock -l1($JOB),-l2($JOB) ; Release locks to tell parent this parent is done
Quit ; Jobbed processes terminate here
;
dostep(first,last) ; Calculate the maximum number of steps from first through last
New current,currpath,i,n
For current=first:1:last Do
. Set n=current ; Start n at current
. Kill currpath ; Currpath holds path to 1 for current
. ; Go till we reach 1 or a number with a known number of steps
. For i=0:1 Quit:$Increment(reads)&($Data(^step($$inttostr(n)))!(1=n)) Do
.. Set currpath(i)=n ; log n as current number in sequence
.. Set n=$Select('(n#2):n/2,1:3*n+1) ; compute the next number
.. Set:n>highest highest=n ; see if we have a new highest number reached
. Do:0<i ; if 0=i we already have an answer for n, nothing to do here
.. If 1<n Set i=i+$$strtoint(^step($$inttostr(n)))
.. TStart () ; Atomically set maximum
.. Set:i>$Get(^result) ^result=i
.. TCommit
.. Set n="" For Set n=$Order(currpath(n)) Quit:""=n Set:$Increment(updates) ^step($$inttostr(currpath(n)))=$$inttostr(i-n)
Quit
This program runs the enhanced benchmark, the difference from the pure numeric benchmark being that instead of storing a database node ^cycle(11) with a value 15, it stores a database note ^cycle("eins eins") with a value "eins пять". The actual strings used for each digit are specified in the comments of the source program at label 15. The strings are actually encoded in UTF-8 to demonstrate that the database is not limited to ASCII or an ISO-8859 variant (in fact, the keys and values can be any arbitrary sequence of bytes).
Database Configuration
Block size - 4096 bytesGlobal buffers - 5000
Journal buffers - 2000
Type of journaling - before image (for backward recovery)
The journal file and database were on the same disk. This is not how production systems are configured, but my laptop has only one hard drive. If the database and journals were on separate disks, performance may be a little better.
Licenses
GT.M is licensed under GNU Affero General Public License version 3.Results
I ran the benchmark three times. I have manually colored the outputs below to improve readability.$ mumps -run threeen1e <.fis-gtm/threeen1.dat
1 100,000 4 8 350 1,570,824,736 6 221,796 1,021,796 36,966 170,299
1 100,000 8 8 350 1,570,824,736 6 221,186 1,021,186 36,864 170,198
1 1,000,000 4 8 524 56,991,483,520 62 2,296,210 10,296,210 37,036 166,068
1 1,000,000 8 8 524 56,991,483,520 68 2,289,947 10,289,947 33,676 151,323
$ mumps -run threeen1e <.fis-gtm/threeen1.dat
1 100,000 4 8 350 1,570,824,736 6 221,674 1,021,674 36,946 170,279
1 100,000 8 8 350 1,570,824,736 6 220,975 1,020,975 36,829 170,163
1 1,000,000 4 8 524 56,991,483,520 69 2,297,107 10,297,107 33,291 149,233
1 1,000,000 8 8 524 56,991,483,520 67 2,299,968 10,299,968 34,328 153,731
$ mumps -run threeen1e <.fis-gtm/threeen1.dat
1 100,000 4 8 350 1,570,824,736 7 222,972 1,022,972 31,853 146,139
1 100,000 8 8 350 1,570,824,736 6 221,596 1,021,596 36,933 170,266
1 1,000,000 4 8 524 56,991,483,520 60 2,308,976 10,308,976 38,483 171,816
1 1,000,000 8 8 524 56,991,483,520 61 2,275,655 10,275,655 37,306 168,453
$
I was very surprised at how large the largest numbers encountered were - for example, the 56,991,483,520 encountered for a range with an upper limit of 1,000,000.
Since the results seemed reasonably consistent and predictable, I decided to run them on a much larger range. I knew that although I would have space on my laptop for the database, I would not have space for the journal files. So, set the limit at which GT.M switches journal files to around 500MB, and baby sat the following run, deleting older generation journal files whenever GT.M switched. So, this is not a good measure of database performance because the IO subsystem was deleting large files concurrent with creating large files. But I am astounded at the largest number encountered.
$ echo 1 10000000 4 | mumps -run threeen1e
1 10,000,000 4 8 685 60,342,610,919,632 3,120 23,417,210 103,417,210 7,506 33,147
$
No comments:
Post a Comment