HHC MMC Programming challenge inC code



#2

The programming challenge at HHC MMX was to write a UserRPL program to sort a list of integers with the odd numbers appearing first and the even numbers appearing second. Entries were scored based on the run-time multiplied by the program size.

Just for fun, I wrote a solution in C code. Although this was clearly an invalid entry for the contest, I wanted to see if the huge increase in size would be offset by the increase in speed.

The UserRPL programs can be found here.

Here are the results. The input lists L10, L100 and L1000 are my own lists of 10, 100, and 1000 random integers. Note that these are not the input lists used by Joe Horn to judge the contest. Size is in bytes and runtime in seconds. Program names are as given in the link above, except that "dh2.c" is my C code implementation.

			PROGRAM
BVB PRGM2 PRGM3 PRGM4 PRGM5 dh2.c
size 98.5 90 99 90 141 16433

Run Time:
L10 0.27 0.42 0.40 1.15 0.90 0.05
L100 2.11 5.55 5.58 7.70 9.93 0.09
L1000 40.25 452.00 211.67 114.90 152.30 0.30

Score (run time * size)
L10 26.1 38.1 40.0 103.6 127.4 828.2
L100 208.2 499.3 552.7 693.1 1400.5 1465.8
L1000 3964.5 40680.0 20955.2 10341.1 21474.3 4865.8

The C code is more than 100 times bigger than the biggest User RPL solution. For a 10-item list, it runs about 5 to 18 times faster, resulting in a "bytes times seconds" score far worse than any of the other programs. But when the list is 1000 items, it runs more than 100 times faster than the fastest User RPL program, which is itself almost three times faster than the next fastest entry. At 1,000 items, the C code's overall score is a close second place to the Bill Butler's winning program.

Note that with a 50G, it's easy to store the C program on an SD card and access it with a small stub program that just recalls and evaluates it.

Here is the C code:

#include <hpgcc49.h>
#include "hpobjects.h"

// Callback function for quicksort. Sort by odd/even then by size
int
cmp(const void *p1, const void *p2)
{
long long ll1, ll2;
int mod1, mod2;

ll1 = *(long long*)p1;
ll2 = *(long long*)p2;

mod1 = ll1 % 2;
mod2 = ll2 % 2;

if (mod1 && !mod2) {
// ll1 odd, ll2 even
return -1;
} else if (!mod1 && mod2) {
return 1;
}

// both are odd or both are even
if (ll1 < ll2) return -1;
if (ll1 > ll2) return 1;
return 0;
}

int main()
{
SatAddr oldList, newList;
SatAddr listOb, iter;
int size, i, j;
SatAddr *arr;
long long *llArray;

sys_slowOff();
if (!STACKdepth()) {
return 0;
}
oldList = STACKpop();
if (!isLIST(oldList)) {
STACKpush(oldList);
return 0;
}

size = LISTsize(oldList);
arr = calloc(size, sizeof(SatAddr));
llArray = calloc(size, sizeof(long long *));

// Get the objects from the list
i = 0;
for (listOb = LISTfirstOb(oldList, &iter);
listOb;
listOb = LISTnextOb(&iter)) {

if (isZINT(listOb)) {
ZINTdecodell(listOb, &llArray[i++]);
}
}

qsort(llArray, i, sizeof(long long), cmp);

for (j=0; j < i; ++j) {
arr[j] = ZINTencodell(llArray[j], 0);
}
newList = LISTencodeN(i, arr, 0);
STACKpush(newList);
free(llArray);
free(arr);
sys_slowOn();
return 0;
}


#3

David,

Thanks for the interesting read.

It inspired me to find out how ND1 (http://naivedesign/ND1) would do on this challenge.

Here's my would-be entry:

  f(v)=v.sort(function(a,b){return(a&1&&!(b&1))?-1:(!(a&1)&&b&1?1:a-b)})

71 bytes.

This code is MorphEngine's "natural math" syntax for maximum compaction.

Easier to read (but slightly larger; and we're sweating bytes here…), it would be written like this:

  function(v) {

return v.sort(function(a, b) { return (a%2 && !(b%2)) ? -1 : (!(a%2) && b%2 ? 1 : a-b); });

}

Run-time for a 1000-element vector is 0.035s on my iPhone 3GS.
B*T score would be ~2.5 (71*0.035).

Run-time for the original 64-element vector from the competition is 0.002s. Score: 0.142

(That's almost a factor 1000 higher than the UserRPL winner.)

Run-time for a 100,000-element vector (generated in a little over a second) is 5.9s.

The integer vector is created either through this RPL program

  \<< \-> n \<< [] 1 n START RAND 2E12 * RND 1E12 - + NEXT \>> \>>

or, for higher speed, this equivalent JavaScript program

  function (n) {

var v = [];

for (var i=0; i<n; i++)

v.push(Math.floor(Math.random()*2e12)-1e12);

return v;

}

Note, that iPhone and 50g use the same CPU architecture (ARM9), but the iPhone is clocked ~10x faster.

Interesting, though, that this advantage is not (at least partially) lost by the interpreter vs. compiled difference.


#4

Quote:
Interesting, though, that this advantage is not (at least partially) lost by the interpreter vs. compiled difference.


It's probably using just-in-time compilation. Basically the interpreter compiles blocks of code as it encounters them and caches the results. The next time it encounters that block of code, it can execute the compiled block. This usually results in interpreted code running nearly as fast as compiled code. That's why java applications usually run pretty quickly.

#5

David,

You're probably right. SquirrelFish Extreme (Nitro) is the JavaScript engine in Safari and, yes, it's JIT'ed. I don't know if Mobile Safari uses the same engine (the older JavaScriptCore engine had no JIT compiler).

I can tell you that in many instances JavaScript code does perform quite a bit slower than C code, as one might expect.
I'm working on a bridge that allows me to use C code (specifically, vectorized code) from JavaScript for greater speed.

#6

Hello all, I'm still trying to figure out what is happening in the winning RPL program in the link. They are all amazing, but what is
STREAM doing with the stack? It's mysterious, because going step by step leaves a list with the size on top. Debug seems impossible with this parallel list processing. Any help? cheers, Glenn


#7

Quote:
Debug seems impossible with this parallel list processing

Try adding a HALT in the code object which is STREAMed:

  \<< I\->R SORT DUP SIZE 3. ROT +
\<< HALT
DUP R\->I SWAP 2. MOD { OVER ROLLD } { UNROT 1. + } IFTE
\>> STREAM DROP \->LIST
\>>

Now you can SST into that code section as well. The top of the stack keeps track of where the odd numbers are inserted. With each even number inserted this pointer is incremented.

HTH

Thomas

PS: Just tested this on a HP-48 emulator, but I assume this is similar on the HP-50.


#8

Thank you Thomas, that did it - I could follow the ifte process, and the use of that counter to let higher odd numbers "hop over" the accumulated even numbers in the stack. Amazing what these RPL experts can do with the tools available. Regards, Glenn


#9

You might want to compare the programs in message #5 and #6 of this previous Programming Challenge.

STREAM (or fold or reduce in other programming languages) is a powerful tool though some consider it harmful.

Cheers

Thomas

Edited: 28 Dec 2010, 12:08 p.m.

#10

Quote:
Hello all, I'm still trying to figure out what is happening in the winning RPL program in the link. They are all amazing, but what is
STREAM doing with the stack? It's mysterious, because going step by step leaves a list with the size on top. Debug seems impossible with this parallel list processing. Any help? cheers, Glenn

Glenn,

I have submitted an article to Datafile that analyzes all five entries to the programming challenge.

Dave


Possibly Related Threads...
Thread Author Replies Views Last Post
  HP PRIME: APP program code DISAPPEARS !! Joseph Ec 0 152 11-25-2013, 11:35 AM
Last Post: Joseph Ec
  HHC 2013 RPN Programming Challenge - Final Thought Jeff O. 7 386 10-17-2013, 11:02 AM
Last Post: Jeff O.
  HHC 2013 programming contest winners Brian Walsh 52 1,965 09-26-2013, 11:39 PM
Last Post: David Hayden
  Box left at HHC Tim Wessman 1 213 09-26-2013, 11:05 PM
Last Post: Wlodek Mier-Jedrzejowicz
  HHC 2013 speakers' files Joe Horn 2 223 09-26-2013, 02:51 AM
Last Post: Geoff Quickfall
  Where to the 32-bit version of User Code Utiltiy for HP-41 ? Olivier (Wa) 2 185 09-26-2013, 01:55 AM
Last Post: Olivier (Wa)
  HHC 2013 Day 2 Highlights Eddie W. Shore 6 431 09-23-2013, 04:03 PM
Last Post: Kimberly Thompson
  HHC 2013: Day 1 Highlights Eddie W. Shore 28 1,084 09-23-2013, 03:22 PM
Last Post: Brad Barton
  HHC / HP Museum Programming Contest for RPN and RPL machines Gene Wright 18 795 09-22-2013, 09:39 AM
Last Post: Miguel Toro
  A HP42S Code Editor Andreas 9 503 09-22-2013, 03:17 AM
Last Post: Andreas

Forum Jump: