RFC: Cross-language benchmark proposal
[1/32] from: joel::neely::fedex::com at: 7-Nov-2002 9:59
Here's a more concrete proposal, based on previous discussions.
I'm posting this to ask for responses/critiques/suggstions/etc.
Let's start small, and add "features" as resources become available
and reader interest demands.
Tasks: A subset of the benchmarks on the "Shootout" page (the
ones that can be run in REBOL).
http://www.bagley.org/~doug/shootout/
I'm looking at them now to identify which can be run.
(e.g. Ackermann 3 8 [stack depth issues] and the
client/server task [requires forking a client process]
should be excluded from our test. There's no point in
documenting tasks we can't perform.)
Rationale: They're available, and we have something to
sanity check against for correctness and
rough performance indices. Plus, we can add
other tasks after covering this basic set.
Languages: C, Java, Perl, Python, REBOL
Rationale: Widely available; likely the languages that
prospective REBOL users will have seen.
Coding: Starting with the published versions on "Shootout", with
open contribution from the REBOL community for REBOL
versions in two flavors:
Standard: Submissions must adhere to the "same thing"
rule from "Shootout".
Custom: Any approach that gets the correct results.
Rationale: We must have comparable designs to allow
comparison across languages/sites. The
addition of "custom" entries allows us to
show unique strengths and/or distinctive
approaches of REBOL.
Solutions: Must take the form of an object with two methods:
/setup Takes a single parameter N that specifies the
"size" of the problem to be solved, and does
any configuration/construction of test cases
needed for the task (within the namespace of
the solution's object).
/run Takes a single parameter N that specifies the
"size" of the problem to be solved, and solves
a single instance of that problem. This must
be nondestructive, in the sense that a single
evaluation of /setup could be followed by
multiple evaluations of /run which can all
produce (statistically) equivalent results.
Rationale: This will allow use of a single test harness
(see below) to gather consistent stats. The
value of N depends on the task; for example,
the "Shootout" Ackermann test used N=8 and
timed the computation of ACK 3 N , while the
value of N for the "count lines/words/chars"
test represents the number of copies of the
standard test data file to concatenate for the
test.
Timings: Performed by a test harness that accepts N (as above) and
uses an internal R (repeat count) in a manner similar to
the following (this is a proposal, subject to discussion!)
Scaling: Starting with a supplied initial guess for R,
evaluate /setup N once and R repetitions of
/run N until the total time for all evaluations
of /run is above some limit (e.g. 2 minutes) to
ensure a reasonable basis for timing without
too much interference from clock jitter,
background activity, or REBOL housekeeping
(e.g. gc).
Measuring: Evaluate /setup N and R repetitions of /run N
measuring elapsed time across all repetitions
(excluding /setup). Perform at least 14 such
tests, then discard the smallest 2 times and
largest two times, leaving a sample of 10.
Report the ten times (in decimal seconds) and
their average.
If errors occur during the timings, then
attempt to repeat the test until 14 samples
have been collected, then report as above.
If 14 error-free samples cannot be obtained,
report any samples that could be collected and
report the test as a failure.
Rationale: Statistical stability.
Partipants: Anybody who wants to contribute cycles, under the following
constraints:
Tasks: All results for a given task (run in multiple
languages) must be submitted at one time.
Coverage: Each submitted task must be run on AT LEAST 3
of the languages above.
Submission: In addition to the information specified under
"Timings" above, the configuration of the test
environment must be documented: hardware,
operating system, compiler/interpreter and
version, etc.
Rationale: Comparability, statistical validity, fairness,
and reproducibility. It does us no good to have
a single result for a given test environment.
It doesn't matter whether the absolute time for
C on my Sun E4500 is shorter than the absolute
time for Java on your IBM i890 (yeah, we're both
dreaming... ;-)
Feedback?
-jn-
--
----------------------------------------------------------------------
Joel Neely joelDOTneelyATfedexDOTcom 901-263-4446
[2/32] from: lmecir:mbox:vol:cz at: 7-Nov-2002 17:56
Hi Joel,
> Tasks: A subset of the benchmarks on the "Shootout" page (the
> ones that can be run in REBOL).
>
> http://www.bagley.org/~doug/shootout/
>
> I'm looking at them now to identify which can be run.
> (e.g. Ackermann 3 8 [stack depth issues]
Romano's ACK works (or does it violate any of the principles?):
ack: func [
{by Romano Paolo Tenca}
m [integer!] n [integer!]
/local result
] [
if m = 0 [return n + 1]
if n = 0 [result: ack m - 1 1 return result]
result: ack m n - 1
ack m - 1 result
]
ack 3 8 ; == 2045
[3/32] from: carl:s:rebol at: 7-Nov-2002 9:43
Joel, a nice start.
I agree with the "let's start small" idea. The simpler the better. Even a
few simple comparisons can get the ball rolling and allow the list to grow
from there. The community will be more involved if it's easy to understand
and follow the descriptions, rules, and conclusions.
For instance, we may not want to start with the Ackermann example. Not a
lot of programmers (and especially beginners) are aware or even interested
in what that benchmark indicates. It's not meaningful to them because they
don't relate to it in common programming use. In fact, if it's listed
first, it may scare them away before they see the simpler examples...
because they may conclude that the comparison examples are too academic and
abstract.
-Carl
At 09:59 AM 11/7/02 -0600, you wrote:
[4/32] from: jan:skibinski:sympatico:ca at: 7-Nov-2002 13:56
-- Unable to decode HTML file!! --
[5/32] from: greggirwin:mindspring at: 7-Nov-2002 12:38
Joel et al,
<< Let's start small, and add "features" as resources become available
and reader interest demands. >>
Yes!
<<
Tasks: A subset of the benchmarks on the "Shootout" page (the
ones that can be run in REBOL).
>>
Yes!
<<
Languages: C, Java, Perl, Python, REBOL
>>
What about VB? *Lots* of people use it, though it's not cross-platform.
<<
Coding: Starting with the published versions on "Shootout", with
open contribution from the REBOL community for REBOL
versions in two flavors:
Standard: Submissions must adhere to the "same thing"
rule from "Shootout".
Custom: Any approach that gets the correct results.
>>
As contributions are made, would custom entries for other languages be
allowed as well? Maybe a better question is: is the goal to show off REBOL,
even at the expense of other language proponents crying "foul" because it
gets special treatment?
These are really two different types of benchmarks, right? The Standard
version is an algorithm benchmark; how a language performs using a specified
algorithm. The Custom version is a "result oriented" benchmark. Just
thinking about how to organize things to make that clear.
<<
Solutions: Must take the form of an object with two methods:
Rationale: This will allow use of a single test harness
(see below) to gather consistent stats.
>>
I haven't looked at the tests to know if N is sufficient for all purposes.
Do you envision anything more elaborate being required?
<<
Partipants: Anybody who wants to contribute cycles, under the following
constraints:
Tasks: All results for a given task (run in multiple
languages) must be submitted at one time.
>>
So if I want to contribute, does this mean I need to write the solution in
each language, or is this just for test *result* submissions? What
requirements will there be for implementation contributions? E.g. the
Ackermann example has shown that there may be multiple approaches taken in
REBOL.
--Gregg
[6/32] from: jan:skibinski:sympatico:ca at: 7-Nov-2002 14:23
Jan Skibinski wrote:
> -- Unable to decode HTML file!! --
>
> --
> To unsubscribe from this list, please send an email to
> [rebol-request--rebol--com] with "unsubscribe" in the
> subject, without the quotes.
This is not what I attempted to post. I did not pay much attention
to yesterday's
threads, and erased most of the messages about mailing problems.
Since
escribe still seems to be unaccessable, could anyone explain this
problem
to me?
I only pasted a pure "fixed width" response to a post written
in "variable width" (Netscape).
Thanks,
Jan
[7/32] from: jan:skibinski:sympatico:ca at: 7-Nov-2002 14:50
Reposting: this time not even trying
to use plain text mode.
If the transformation below is compliant
with the contest rules then the 'ack could
be made faster. We could even handle the
case of 'ack 3 9.
Clear definition from Haskell:
------------------------
ack :: Int -> Int -> Int
ack 0 n = n+1
ack m 0 = ack (m-1) 1
ack m n = ack (m-1) (ack m (n-1))
Example transformation for ack 3 3:
-----------------------------------
ack 3 3 = ack 2 (ack 3 2)
= ack 2 (ack 2 (ack 3 1))
= ack 2 (ack 2 (ack 2 (ack 3 0)))
= ack 2 (ack 2 (ack 2 (ack 2 1)))
Compliant so far? If so, then:
Implementation #1:
----------------
{Iterate implements the transformation from above}
iterate: func [f n /local x][x: 1 loop (n + 1) [x: f x] x]
boom0: func [n][n + 1]
boom1: func [x][iterate :boom0 x]
boom2: func [x][iterate :boom1 x]
boom3: func [x][iterate :boom2 x]
>> boom3 8
== 2045
time: 0:00:02.824
>> boom3 9
== 4093
time: 0:00:11.226
Implementation #2 packages the implementation #1,
but slows down quite a bit:
------------------------------------------
ack': func [
m [integer!]
n [integer!]
/local iterate boom
][
iterate: func [f n /local x][x: 1 loop (n + 1) [x: f x] x]
boom: func [
m n
/local f
][
either m = 0 [
n + 1
][
f: func [n][boom (m - 1) n]
iterate :f n
]
]
boom m n
]
>> ack' 3 8
== 2045
time: 0:00:10.446
Romano's version:
----------------
>> ack 3 8
== 2045
0:00:40.689
Regards,
Jan
Ladislav Mecir wrote:
[8/32] from: joel:neely:fedex at: 7-Nov-2002 13:39
Hi, Ladislav,
No, it's not kosher, for the same reason that this isn't:
>> ack-3m: func [m [integer!]] [2 ** (m + 3) - 3]
>> repeat i 8 [print [i ack-3m i]]
1 13
2 29
3 61
4 125
5 253
6 509
7 1021
8 2045
(see below).
Ladislav Mecir wrote:
> Romano's ACK works (or does it violate any of the principles?):
> ack: func [
<<quoted lines omitted: 7>>
> ack m - 1 result
> ]
The above definition isn't "legal" according to the "same thing"
rule (in exactly the same way as the one below that I posted with
the disclaimer yesterday).
The point of the comparison is not to find another way to get the
equivalent result, but to see how long it takes for exactly the
same algorithm to produce the specified result. Both the ACK
above and my ACK5 below break the single compound expression
ack-func m - 1 ack-func m n - 1
into the sequence of simpler expressions
temp: ack-func m n - 1
ack-func m - 1 temp
which calls for slightly different (although functionally
equivalent) behavior. I think it's appropriate to avoid even the
smallest opportunity for someone to accuse us of cooking the
benchmark results (the old "Caesar's wife" principle).
I recall a case from a few years ago in which a compiler vendor
was accused of tweaking their optimizer to recognize certain
commonly-used benchmark expressions and do naughty things that
did not occur for other (normal) code.
ack5: func [m [integer!] n [integer!] /local result] [
max_depth: max max_depth curr_depth: curr_depth + 1
tot_evals: tot_evals + 1
if m = 0 [
curr_depth: curr_depth - 1
return n + 1
]
result: either n = 0 [
1
][
ack5 m n - 1
]
result: ack5 m - 1 result
curr_depth: curr_depth - 1
result
]
The whole point of including a task such as Ackermann would be to
compare/contrast performance on recursively-defined functions. We
can meet the same objective (without hitting implementation limits)
by using some other recursive function, such as:
fib: func [n [integer!]] [
either n < 2 [n][(fib n - 1) + fib n - 2]
]
I'd consider non-comparable any submission in which someone said
You can do IT faster using this function:
cheat: func [n [integer!] /local g] [
g: 2.23606797749979
to-integer (1.0 + g / 2.0 ** n) - (1.0 - g / 2.0 ** n) / g
]
That's not a *bad* approach, just a different one! ;-)
-jn-
--
----------------------------------------------------------------------
Joel Neely joelDOTneelyATfedexDOTcom 901-263-4446
[9/32] from: joel:neely:fedex at: 7-Nov-2002 14:18
Hi, Gregg,
Gregg Irwin wrote:
> <<
> Languages: C, Java, Perl, Python, REBOL
> >>
>
> What about VB? *Lots* of people use it, though it's not cross-
> platform.
>
If enough folks want to see it for comparison purposes, and enough
folks have the means to run the benchmarks (we should have multiple
participants for each benchmark task IMHO for statistical stability)
I (for one) wouldn't throw up major objection (although my personal
suspicion is that the target zones for VB and REBOL have significant
non-overlap).
> <<
> Coding: Starting with the published versions on "Shootout", with
<<quoted lines omitted: 13>>
> oriented" benchmark. Just thinking about how to organize things to
> make that clear.
I agree that there are two issues; I'd suggest that the presentation
of results could clearly separate "standard" submissions and timings
from "custom" submissions. We're not trying to take on the whole
field of algorithm analysis here; just show some points of "compare
and contrast". Also, some of the optimize-by-design issues would
actually require significant expertise in the various languages.
Do we want to worry about finding/developing/cultivating expertise
in all languages, or just provide a fair comparison along with some
other interesting info?
> <<
> Solutions: Must take the form of an object with two methods:
<<quoted lines omitted: 3>>
> I haven't looked at the tests to know if N is sufficient for all
> purposes. Do you envision anything more elaborate being required?
I'm looking at that now (but suspect that we can make sure that a
single integer is enough of a "size" argument in some fashion, as
in the case of the file I/O problem where the "size" is number of
copies of a standard disk file).
> <<
> Partipants: Anybody who wants to contribute cycles, under the following
<<quoted lines omitted: 5>>
> solution in each language, or is this just for test *result*
> submissions?
I see two populations (which may certainly overlap):
Developers - who would write and submit source for the test harness
and the individual tasks, and
Testers - who would retrieve source for the test harnesses and
tasks from a well-known source (once the harnesses and
tasks had been designed and implemented), would run the
tests as supplied, and report results.
I would see a front-end period where Developers would haggle out
details, agree on designs, and make their submissions, after which
the source artifacts would be available to the Testers.
Anyone with the appropriate skills and resources would be free to
offer services as Developer and/or Tester, but there'd be some point
at which a "release" of the sources for harness/tests would be
frozen and made available for testing. Of course, all of this has
to do with the "standard" solutions. The "custom" solutions could
be handled somewhat more informally *after* at least the harness (for
timing submissions) and a canonical "same thing" REBOL solution (for
validity checking) were completed.
> What requirements will there be for implementation contributions?
> E.g. the Ackermann example has shown that there may be multiple
> approaches taken in REBOL.
>
I think we should be fairly picky about the "same thing" rule; there
are tons of ways of writing functionally and algorithmically equivalent
code, and even more ways of writing functionally equivalent code that
uses alternate algorithms. All of that is of no benefit to our Prime
Directive (certainly at least initially) of showing how a *small* set
of specific algorithms for reasonably common tasks perform in REBOL
and a few comparable/competitive languages. Even adding a subordinate
place for "custom" solutions that tweak for REBOL features/idioms is
pushing the border of relevance IMHO, but might help newcomers get the
feel of how the REBOL approach is different from the mindsets of some
other languages.
-jn-
--
----------------------------------------------------------------------
Joel Neely joelDOTneelyATfedexDOTcom 901-263-4446
[10/32] from: joel:neely:fedex at: 7-Nov-2002 14:38
Hi, Jan,
Interesting stuff, and nice to see it posted, but ...
Jan Skibinski wrote:
> If the transformation below is compliant
> with the contest rules then the 'ack could
> be made faster. We could even handle the
> case of 'ack 3 9.
...
> >> ack' 3 8
> == 2045
<<quoted lines omitted: 4>>
> == 2045
> 0:00:40.689
... AFAIAC *any* solution based on "transformation" of the standard
algorithm would go in the "custom" category.
Besides, (although I don't think Ackermann belongs, partly because I
agree with Carl's comments, and partly for other reasons) what if we
decided to benchmark with
ack [3..5] 8
instead?
-jn-
--
----------------------------------------------------------------------
Joel Neely joelDOTneelyATfedexDOTcom 901-263-4446
[11/32] from: greggirwin:mindspring at: 7-Nov-2002 13:41
Joel, Carl et al
I guess the appropriate set of tests to use depends on the goal(s). Do we
want to:
a) Do things like the shoot out, that is fun for supergeeks
who are into language design and implementation.
A.K.A. "Standard"
b) Do things that show how REBOL performs solving real problems,
perhaps in the context of a particular algorithm.
A.K.A. "Custom"
c) Both of the above.
d) Something else?
--Gregg
[12/32] from: jan:skibinski:sympatico:ca at: 7-Nov-2002 16:30
Hi Joel,
> ... AFAIAC *any* solution based on "transformation" of the standard
> algorithm would go in the "custom" category.
>
I do not mind such classification and I do not particularly care
that much about it. You are the boss in this project, so go
ahead, set the rules and I will comply. :-)
I was just fiddling with something else and it suddenly appeared
to me that I could reuse it in Ackerman. I'll post that little
gadget separately.
However I do not understand your quotation marks around my
'transformation word.:-)
A technique of program transformation is considered to be
a good thing, since it quite often offers a refreshing view.
As long as two things are equal they are "referentially transparent".
This is what Haskell is all about (aside from the laziness): you can
always substitute LHS by RHS _everywhere_ in your program
and you do not have to worry about side effects and changes
to semantics. I took great care to comply with this principle
in the example posted.
And here is a fine line: if a compiler did exactly what I have done
you would not complain, would you?
:-)
All the best,
Jan
[13/32] from: carl:cybercraft at: 8-Nov-2002 10:32
On 08-Nov-02, Carl at REBOL wrote:
> For instance, we may not want to start with the Ackermann example.
> Not a lot of programmers (and especially beginners) are aware or
<<quoted lines omitted: 3>>
> away before they see the simpler examples... because they may
> conclude that the comparison examples are too academic and abstract.
Sorting would be one obviously useful example, meaning comparisons of
the languages' built-in sorting ability.
--
Carl Read
[14/32] from: joel:neely:fedex at: 7-Nov-2002 16:38
Hi, Jan,
Jan Skibinski wrote:
> I do not mind such classification and I do not particularly care
> that much about it. You are the boss in this project, so go
> ahead, set the rules and I will comply. :-)
>
Heavens to Murgatroyd, no! ;-) I'm just contributing my opinion
and everyone else is free to do so as well!
> I was just fiddling with something else and it suddenly appeared
> to me that I could reuse it in Ackerman. I'll post that little
> gadget separately.
>
I'm eager to see it.
> However I do not understand your quotation marks around my
> 'transformation word.:-)
>
Only because I was quoting it, not taking credit for the idea! ;-)
> A technique of program transformation is considered to be
> a good thing, since it quite often offers a refreshing view.
>
I completely agree, especially if we're talking about computing and
programming in general. But when we're comparing implementations
of programming languages, I think it's reasonable to put the focus
on what the *implementations* can do with the same design, rather
than how clever different *programmers* can be at coming up with
variations on the design.
> As long as two things are equal they are "referentially
> transparent". This is what Haskell is all about (aside from the
> laziness): you can always substitute LHS by RHS _everywhere_
> in your program and you do not have to worry about side effects
> and changes to semantics. I took great care to comply with this
> principle in the example posted.
>
We're emphatically in agreement here about the desirability of
referential transparency as a principle of programming and language
design. (In the past I think I offended some people by pointing
out lapses of ref. trans. in REBOL.) But, again, that was in a
different context than the present discussion of benchmarking how
well different implementations of different languages handle a
high-level description of an algorithm.
> And here is a fine line: if a compiler did exactly what I have
> done you would not complain, would you?
>
No. And let me give a concrete example. Suppose I wanted to test
how efficiently some language handled looping and simple arithmetic,
and so wrote something like the following:
loop-and-add: func [n [integer!] /local t i sum] [
t: now/time/precise
i: sum: 0
loop n [
sum: sum + i: i + 1
]
t: to-decimal now/time/precise - t
print [n sum t]
]
I might also want to test how efficiently the language handled
recursion, and so might write something like this:
recur-and-add: func [n [integer!] /local t sum] [
t: now/time/precise
sum: _recur-and-add 0 n
t: to-decimal now/time/precise - t
print [n sum t]
]
_recur-and-add: func [t [integer!] n [integer!]] [
either n = 0 [t] [_recur-and-add t + n n - 1]
]
If another programmer came along and observed, "You know that
you can perform the computation of both of these functions faster
with this:
triangle-sum: func [n [integer!]] [print [n n + 1 * n / 2 0]]
so why not use that instead?", then I'd have to respond, "Because
I want to see how smart the compiler/interpreter is, not test my
own abilities."
OTOH, if the compiler/interpreter had an optimizer that could
accept the sources for LOOP-AND-ADD and RECUR-AND-ADD and auto-
matically transform either/both into TRIANGLE-SUM, then I'd be
very happy indeed with the implementation!
Same issue as with tail-recursion-elimination (an issue which
comes up on the list every so often). As human programmers go,
it should be old news, but it's still significant to know
whether a given language implementation can do it automatically.
-jn-
--
----------------------------------------------------------------------
Joel Neely joelDOTneelyATfedexDOTcom 901-263-4446
[15/32] from: joel:neely:fedex at: 7-Nov-2002 16:42
Hi, Carl,
That's a really good point!
Carl Read wrote:
> Sorting would be one obviously useful example, meaning comparisons
> of the languages' built-in sorting ability.
>
And we could have both native-sort and hand-coded sort tests (e.g.
some reasonable algorithm such as heapsort or Quicksort) as a QAD
index into how much leverage was obtained by using the built-in sort
facility in each language.
-jn-
--
----------------------------------------------------------------------
Joel Neely joelDOTneelyATfedexDOTcom 901-263-4446
[16/32] from: jan:skibinski:sympatico:ca at: 7-Nov-2002 20:34
Hi Joel,
> Heavens to Murgatroyd, no! ;-) I'm just contributing my opinion
> and everyone else is free to do so as well!
That was a booby trap of mine :-)
I have no other comments about your last response.
I have to agree with most of it. BTW, you did
s good job with your proposal.
I am attaching the little gadget I mentioned
before.
All the best
Jan
> >
> > I was just fiddling with something else and it suddenly appeared
> > to me that I could reuse it in Ackerman. I'll post that little
> > gadget separately.
> >
>
> I'm eager to see it.
>
-----------------------------------------------------
It's really nothing, a little gadget, but quite covenient,
because it abstracts away and composes
many functions into one.
Something similar to operator (.) in Haskel, as in:
f = g . h . k
It also allows for making quick and dirty
temporary functions:
pipe: func [
{Make a pipeline from a block of functions}
fs [block!]
/local result [function!]
][
make function! [x] append copy fs 'x
]
filter pipe [6 < ] .. [1 20]
map pipe [10 * sine] ..[1 10]
g: pipe [10 * sine]
source g
==g: func [x][10 * sine x]
Do you recognize this?
g: pipe [boom2 boom2 boom2 boom2]
g 1
== 61
Well that's ack 3 3 from the example I previously posted.
How about putting a probe after each stage of the pipeline?
[17/32] from: carl:cybercraft at: 8-Nov-2002 19:11
On 08-Nov-02, Joel Neely wrote:
> Suppose I wanted to test
> how efficiently some language handled looping and simple arithmetic,
<<quoted lines omitted: 34>>
> it should be old news, but it's still significant to know
> whether a given language implementation can do it automatically.
Those are good points. I do think there's room for both "Standard"
and "Custom" algorithms though, as they show up different strengths
in a language. The standard ones could be considered to be comparing
raw performance, whereas with the custom ones you'd be comparing how
programmers would normally approach a given problem in the different
languages. What would be considered a normal approach is subjective
of course, but if the committee in charge of choosing an example all
agree that it's both readable and elegant and not unusually tricky
code, then that should be good enough. I feel custom code would give
a better indication of developement time and ease of maintainance
than standard algorithms, as well as showing off "the REBOL way" of
writing code.
--
Carl Read
[18/32] from: atruter:labyrinth:au at: 8-Nov-2002 17:53
Hi Joel,
My (perhaps overly simplistic) perspective is that I'd want to see a large table with
each column having a different language and each row containing a basic
language construct. If a particular language does not support that construct then the
nearest functional equivalent is used, or a note provided indicating its
absence in the target language.
Beneath each code fragment some quantified benchmark results would be given. Deriving
the "units" of comparison would be the hardest and most politically sensitive
part! ;) Beneath this might be some, perhaps subjective, ways of measuring the code.
A typical entry (formatted as a row) might read:
Construct
foreach
Benchmark
Integer: 1,000,000 integers
String: 1,000,000 strings of length 1-255
REBOL
foreach val values []
Integer Benchmark: n units
String Benchmark: n units
Efficiency: ***
Compactness: ****
Clarity: *****
PERL
foreach $val (@values) {}
Integer Benchmark: n units
String Benchmark: n units
Efficiency: ****
Compactness: ***
Clarity: ****
This would allow folks to see how the fundamental building blocks of each language are
implemented and give a rough guide as to where the strengths and weaknesses
of each are. I remember when first starting with REBOL often saying to myself, "In PERL
I would break this down into steps A, B, C which can be done in Pascal as A,
B or C; or in some completely alien way in REBOL!" ;)
I know that people have to "think different" when using REBOL, but most simple constructs
are present and that is what folks looking at REBOL for the first time and
/ or comparing it to something else will want to see initially.
Regards,
Ashley
[19/32] from: greggirwin:mindspring at: 8-Nov-2002 9:45
Hi Joel,
<< (although my personal suspicion is that the target zones for VB and REBOL
have significant non-overlap). >>
UI creation may be seen as their major zone of overlap, but VB is a general
purpose language just like all the others so I wouldn't classify it as being
very different, except for being a Windows-only solution.
My view is based on my background and exeperience, where people buy
commercial products and laugh heartily when you talk about downloading
source and compiling a tool yourself in order to use it, but it's perfectly
normal to spend a few weeks trying to get an InstallShield setup built after
a product is ready. :)
<<
Also, some of the optimize-by-design issues would
actually require significant expertise in the various languages.
Do we want to worry about finding/developing/cultivating expertise
in all languages, or just provide a fair comparison along with some
other interesting info?
>>
I like that latter view. A fair comparison plus interesting info. I also
think that if the tests are easy to implement, the expertise will come to
us.
<< I think we should be fairly picky about the "same thing" rule >>>
I agree.
--Gregg
P.S. Thanks for heading this up. -G
[20/32] from: gerardcote:sympatico:ca at: 8-Nov-2002 12:19
Hi, Gregg and al,
...
> Languages: C, Java, Perl, Python, REBOL
> >>
>
> What about VB? *Lots* of people use it, though it's not cross-platform.
>
> <<
I agree with your pov about VB and I will submit my own stuff regarding this language
with help welcome from others too. As soon as
my &?%$* roof is completely covered - again a small couple of days if Mother Nature is
along with me ... (this simply means not too
much SNOW as the one I got yesterday - it's too soon but will nevertheless be FUN when
I will be doing SKI - must be kept positive
somehow...)
See you later,
Keep up the good work gang!
Gerard
P.S. We're on the good way - I never thought (but in fact secretly dreamed of ...) ALL
of this COMMON EFFORT to document REBOL for
the "Other World" could have been raised so quickly by so many "talented" contributors
and so many newbies too - as I am one
myself...
[21/32] from: greggirwin:mindspring at: 8-Nov-2002 10:38
Lots of good ideas flowing here, which brings me back to a question I posted
but that people may not have had a chance to respond to.
What is our goal?
REBOL, being a pure inpterpreter is going to be at a disadvantage in some
areas, but have advantages in others. Benchmarking things like sorting is
nice because you need to do it all the time. If it's native to a language,
it's sort of like benchmarking a compiler's optimizations, except that
you're comparing the compiler used to build the language *and* the design of
the sort function. Only the result matters though. In the case of SORT, you
can have simple and complex tests (e.g. multi-column sorts, sorting a series
of objects or structures, etc.) which may show the various levels of sorting
support in a language.
Maybe the Standard and Custom views are more like a distinction between
academic
and "applied"? The Academic view is like the other shootout, and
the Applied view is comparing how you would actually use it on a daily basis
and how ranks in that context (speed, clarity, etc.).
What do you think?
--Gregg
[22/32] from: joel:neely:fedex at: 8-Nov-2002 14:04
Hi, Gregg,
Gregg Irwin wrote:
> Lots of good ideas flowing here, which brings me back to a
> question I posted but that people may not have had a chance
> to respond to.
>
> What is our goal?
>
I thought I *did* address that question with a short list of
(what I thought were) reasonable goals, and Carl S indicated his
preference for the first one on the list.
> ... I like Option 1.
> And, we know between us that we're not trying to convert
<<quoted lines omitted: 12>>
> REBOL, being a pure inpterpreter is going to be at a disadvantage
> in some areas, but have advantages in others.
Where do you see a "disadvantage"? Of the languages I proposed...
> Languages: C, Java, Perl, Python, REBOL
... *all* of the others but C are usually implemented via interpreter.
I don't have any firm preconceived notions about what the results will
look like (except for C usually being fastest), but let's not be too
quick to wave the white flag just because REBOL isn't the fastest
language for all tests! Brute speed is only one of many factors that
go into a language decision, and for 90% of what I do, "fast enough"
is the key issue, rather than "fastest".
> Maybe the Standard and Custom views are more like a distinction
> between "academic" and "applied"? The Academic view is like the
> other shootout, and the Applied view is comparing how you would
> actually use it on a daily basis and how ranks in that context
> (speed, clarity, etc.).
>
> What do you think?
>
It's interesting that I would have reversed the labels. My original
intent was for the tasks to be small but realistic ("applied") in
nature, and the "standard" solution to be the kind of thing that a
reasonable programmer (though not a Grand Master of any particular
language) would think to write. The custom solutions, where the
esoterica of a particular language's world view emerge, seems much
more "academic" to me.
-jn-
--
----------------------------------------------------------------------
Joel Neely joelDOTneelyATfedexDOTcom 901-263-4446
[23/32] from: edanaii:cox at: 8-Nov-2002 18:40
Carl Read wrote:
>Those are good points. I do think there's room for both "Standard"
>and "Custom" algorithms though, as they show up different strengths
<<quoted lines omitted: 8>>
>than standard algorithms, as well as showing off "the REBOL way" of
>writing code.
The algorithm for any program should be specified in simple English. It
should be void of any technical references nor should it suggest any
technical solutions.
For example, the algorithm for the RandomCopy procedure I mentioned
earlier is:
* Specify Source Directory
* Specify Target Directory or File
1 Get all the files in the Source Directory.
2 Choose one file randomly.
3 Copy it to the Target File or Directory.
Stating it this way keeps it at a "logical" level and should avoid any
subjective
issues as the only constraints here are the resources being
utilized. I.e. Files and directories.
--
Sincerely, | There are many humorous things in the world: among
Ed Dana | them the white man's notion that he is less savage
Software Developer | than the other savages.
1Ghz Athlon Amiga | -- Mark Twain
[24/32] from: carl:cybercraft at: 9-Nov-2002 18:42
On 09-Nov-02, Ed Dana wrote:
> Carl Read wrote:
>> Those are good points. I do think there's room for both "Standard"
<<quoted lines omitted: 22>>
> any "subjective" issues as the only constraints here are the
> resources being utilized. I.e. Files and directories.
Okay. And I'd write that something like this, (though with a filled
header of course), ...
rebol []
dir: %test-dir/
file: %test-dir/random-file
write/binary file read/binary join dir random/only read dir
Would Joel approve though? (;
--
Carl Read
[25/32] from: joel:neely:fedex at: 9-Nov-2002 8:09
Hi, Carl, and all,
I think we're making this WAAAAAY harder than it needs to be!
(And I'll accept my full share of responsbility... ;-)
Carl Read wrote:
> On 09-Nov-02, Ed Dana wrote:
>
> > The algorithm for any program should be specified in simple
> > English. It should be void of any technical references nor
> > should it suggest any technical solutions.
>
The issue which concerns me (and which I accept responsibility
for not communicating clearly) is that we're trying to compare
*language*implementations* and not *programmers*. Therefore
we have to be clear about how much latitude is allowed to the
author of a test solution, and only compare solutions that are
fairly comparable.
Suppose we had a task specified as follows:
- Generate a list/array of 10000 random integers, each
between 1 and 1000000;
- Sort the array into ascending order;
- Sort the result into descending order.
Now suppose we get the following submissions:
Program Programmer Algorithm Language
------- ---------- ------------- --------
A Alice bubblesort REBOL
B Bob quicksort REBOL
C Clara built-in SORT REBOL
D Don bubblesort Perl
E Ethyl build-in SORT Perl
We could compare A and D to get an idea of how the languages
compare in their handling of looping and array/block access
speeds.
We could compare C and E to get an idea of how the languages
compare in their fastest possible sorting mechanisms (I'm
assuming that the built-in SORT facilities are faster than
someone could rewrite in interpreted code).
But comparing B with *any* other submission doesn't IMHO give
us any meaningful compare-REBOL-with-Perl information (although
it *does* tell us that Bob wrote a more sophisticated algorithm
than Alice, and it might tell us just how much gain a REBOL
programmer could realize by using SORT instead of a home-grown
function).
Given those five submissions, I'd suggest that we probably ought
to split that hypothetical problem above into two tasks:
1) Solve the sorting problem above, using bubblesort according
to the following pseudo-code specification ...; and
2) Solve the sorting problem above, using the fastest sorting
means you can come up with.
Then I'd view A and D as solutions to (1); C and E would make
good solutions to (2); I don't think it would be reasonable to
compare e.g. A with E (or B with D) and think I was thereby
making a fair compare/contrast examination of REBOL and Perl.
> > For example, the algorithm for the RandomCopy procedure I
> > mentioned earlier is:
<<quoted lines omitted: 12>>
> file: %test-dir/random-file
> write/binary file read/binary join dir random/only read dir
That seems quite reasonable for the problem as stated. Now, let's
suppose that some novice C programmer wrote a submission that was
structured as follows:
1) Recursively traverse the entire file system from the root
directory, performing the following for each fully-pathed
file name encountered:
1.1) If the encountered name is a complete prefix match to
the specified source directory, and there are no more
slashes in the remainder of the encountered name,
allocate a buffer to hold the name, copy the name into
the buffer, and store a pointer to the buffer into the
array of file names. Oh, by the way, if that filename
array is full, allocate a new one twice the size, copy
all existing pointers into the new one, and then append
the new name pointer.
2) After traversing the entire file system, shuffle the array
of file name pointers, using a bubble sort algorithm with
a comparison function that returns random results.
3) Open the file whose name is in the middle of the shuffled
array.
...
I've already gone on too long, but pretend that the rest of the
program is as BBD as the above. Now, what would we learn about
C and REBOL by comparing that program with your three-liner?
(For extra credit, what would we learn about the kind of twisted
mind that could come up with such an obviously wrong-headed
algorighm? ;-)
-jn-
--
; Joel Neely joeldotneelyatfedexdotcom
REBOL [] do [ do func [s] [ foreach [a b] s [prin b] ] sort/skip
do function [s] [t] [ t: "" foreach [a b] s [repend t [b a]] t ] {
| e s m!zauafBpcvekexEohthjJakwLrngohOqrlryRnsctdtiub} 2 ]
[26/32] from: g:santilli:tiscalinet:it at: 9-Nov-2002 16:52
Hi Joel,
On Saturday, November 9, 2002, 3:09:32 PM, you wrote:
JN> (For extra credit, what would we learn about the kind of twisted
JN> mind that could come up with such an obviously wrong-headed
JN> algorighm? ;-)
Mind you, I know at least one guy that would come up with
something like that. :-) (I had to fix his VB code a couple times,
but to really fix his code one should disallow him to code. :)
Regards,
Gabriele.
--
Gabriele Santilli <[g--santilli--tiscalinet--it]> -- REBOL Programmer
Amigan -- AGI L'Aquila -- REB: http://web.tiscali.it/rebol/index.r
[27/32] from: greggirwin:mindspring at: 9-Nov-2002 12:27
Hi Joel,
>> >Option 1
>> >>> >
<<quoted lines omitted: 5>>
>> >Audience: Developers at large.
>> >
I'm probably just not saying what I'm thinking very clearly, or my
mind was on a different track (read - derailed :).
In any case, yes, the above goal is stated clearly, and your other
replies have helped also. My question was targeted at the
implementation of the test (custom versus standard) with this overall
goal in mind. I.e. we have to sub-goals.
JN> Where do you see a "disadvantage"? Of the languages I proposed...
Sorry, I was thinking in more general terms than just the languages
currently proposed. However, Java is at least byte-code compiled in
all cases, correct? It may be JIT'd as well. C is the reference point,
so it is a special case IMO (i.e. how fast *could* something run).
JN> I don't have any firm preconceived notions about what the results will
JN> look like (except for C usually being fastest), but let's not be too
JN> quick to wave the white flag just because REBOL isn't the fastest
JN> language for all tests! Brute speed is only one of many factors that
JN> go into a language decision, and for 90% of what I do, "fast enough"
JN> is the key issue, rather than "fastest".
Agreed. No white flags here.
JN> It's interesting that I would have reversed the labels. My original
JN> intent was for the tasks to be small but realistic ("applied") in
JN> nature, and the "standard" solution to be the kind of thing that a
JN> reasonable programmer (though not a Grand Master of any particular
JN> language) would think to write. The custom solutions, where the
JN> esoterica of a particular language's world view emerge, seems much
JN> more "academic" to me.
My thinking is that the "acadaemic" version refers to something that is worth
knowing (how it performs against a particular algorithm) but isn't
what you would actually use on a day-to-day basis. "applied" is what
you do (e.g. calling SORT rather than writing your own -
notwithstanding special cases where SORT just won't do). Maybe the
esoteric solutions are a third category, though I don't know how much
we want to fragment things. I don't know that esoteric solutions are
really useful in this context. If you're talking about solving
problems in unique and interesting ways, yes, but not here.
--Gregg
[28/32] from: edanaii:cox at: 9-Nov-2002 10:20
Joel Neely wrote:
>Hi, Carl, and all,
>I think we're making this WAAAAAY harder than it needs to be!
<<quoted lines omitted: 51>>
>compare e.g. A with E (or B with D) and think I was thereby
>making a fair compare/contrast examination of REBOL and Perl.
I guess I'm confused by your point, Joel.
To simplify the discussion, let's say that Fred submitted something:
Program Programmer Algorithm Language
------- ---------- ------------- --------
F Fred QuickSort Perl
Then could you not compare B to F?
This is exactly why I was suggesting that an algorithm be submitted
first, and then languages be compared on the basis of their compliance
to the algorithm.
Or am I missing something?
>>>For example, the algorithm for the RandomCopy procedure I
>>>mentioned earlier is:
<<quoted lines omitted: 28>>
> directory, performing the following for each fully-pathed
> file name encountered:
Please note that in the algorithm, recursion was not specified. If a
hot-shot wants to include recursion fine, but it should not be
considered as having met the criteria of the algorithm.
A new algorithm could be specified that includes recursion, and then new
submissions be made to implement it.
> 1.1) If the encountered name is a complete prefix match to
> the specified source directory, and there are no more
<<quoted lines omitted: 5>>
> all existing pointers into the new one, and then append
> the new name pointer.
As long as it supports the algorithm, any additional steps taken to meet
it can be used as a measure of how much it took to implement the code.
> 2) After traversing the entire file system, shuffle the array
> of file name pointers, using a bubble sort algorithm with
> a comparison function that returns random results.
>
> 3) Open the file whose name is in the middle of the shuffled
> array.
>
> ...
>
Again, we've gone beyond the basic specification.
Competitors should match the criteria, no more, no less. They should not
infer anymore than what is specified by design. If they do otherwise,
they should submit a new algorithm.
--
Sincerely, | Cold Hearted Orb, that rules the night. Removes
Ed Dana | the colours from our sight! Red is gray and
Software Developer | yellow white! But we decide which is right...
1Ghz Athlon Amiga | And which is an illusion!
| -- The Moody Blues, Late Lament.
[29/32] from: edanaii:cox at: 9-Nov-2002 7:50
Carl Read wrote:
>On 09-Nov-02, Ed Dana wrote:
>>The algorithm for any program should be specified in simple English.
<<quoted lines omitted: 25>>
>write/binary file read/binary join dir random/only read dir
>Would Joel approve though? (;
Looks like your solution is close to my solution, with only some minor
differences.
======================================================================
REBOL [
Title: "Random Copy"
File: %RandomCopy.r
Date: 28-Oct-2002
Purpose: {
Copies a file from the source directory specified to the
target directory or file.
}
]
RandomCopy: Func [
{Copies one randomly chosen file owned by the source directory to the
target file or directory.
}
;* Specify Source Directory
SourceFile [File!] "The directory containing the files to be copied."
;* Specify Target Directory or File
TargetFile [File!] "The Target directory/file to be copied to."
] [
;1 Get all the files in the Source Directory.
Files: read SourceFile
;2 Choose one file randomly.
Random/Seed Now
;3 Copy it to the Target File or Directory.
Write TargetFile Read to-file join SourceFile Pick Files Random
Length? Files
]
======================================================================
First, I chose to create mine as a function, for repeatable purposes. I
actually use it. :) It chooses my sig file, for example.
Second, as part of my algorithm, I had specified a Source and Target
directory. I met that specification, in part by creating it as a function.
Third, I chose to use Random/Seed to insure true randomness. At least,
it was my perception that it would be truly random. :) So, in this
context, is it any more or less random than your solution?
Also, you chose to Write the file as a binary file. Is this safer? Or
just focused on binary? Just wondering...
I think that this can be graded for "effort" by measuring the number of
steps in the algorithm (5) by the number of actions taken in the
solution (11). Which means it scores about 45% for completeness (5/11),
which is, actually, very good. My java solution scores much worse: 28
actions or 18%.
Admittedly, my Java solution could probably be reduced in the number of
actions taken to meet the algorithm, but what I find interesting about
this situation is that I've known Java longer than I've known REBOL
(1997 vs. 2001) and I wrote my REBOL solution in 1/4 the time and using
considerably less code. :)
Some thoughts:
I'm using the concept of "Actions" to measure the solution against the
algorithm. I was originally thinking of using "Lines of code" to measure
the effort of the solution. I switched to actions because, in Java for
example, you can stack as many commands as you want on a single line.
As I suggested earlier, I personally think such a web site should be
more than just a competition site. I think it should also be a "how to"
site, which is why I chose to make my solution utilitarian. You need a
means to drive people to the site and a reason for them to stay. Once
they find it useful, they'll take a closer look at the other solutions
available and see for themselves who is better and who isn't.
--
Sincerely, | Control is an illusion, you infantile egomaniac.
Ed Dana | Nobody knows what's gonna happen next: not on a
Software Developer | freeway, not in an airplane, not inside our own
1Ghz Athlon Amiga | bodies and certainly not on a racetrack with 40
| other infantile egomaniacs.
| -- Days of Thunder
[30/32] from: carl:cybercraft at: 10-Nov-2002 18:09
On 10-Nov-02, Ed Dana wrote:
> Carl Read wrote:
>> On 09-Nov-02, Ed Dana wrote:
<<quoted lines omitted: 52>>
> Length? Files
> ]
======================================================================
> First, I chose to create mine as a function, for repeatable
> purposes. I actually use it. :) It chooses my sig file, for example.
> Second, as part of my algorithm, I had specified a Source and Target
> directory. I met that specification, in part by creating it as a
> function.
Your...
Specify Target Directory or File
was a bit ambiguious I thought, and I chose file, but I can see how
Target could be either, and my attempt just assumes it's a file.
> Third, I chose to use Random/Seed to insure true randomness. At
> least, it was my perception that it would be truly random. :) So, in
> this context, is it any more or less random than your solution?
Yours would be better, else you'd always get the same results from
startup given an unchanged directory.
> Also, you chose to Write the file as a binary file. Is this safer?
> Or just focused on binary? Just wondering...
If you don't specify binary, it's possible the file could be
changed...
>> ? read
USAGE:
READ source /binary /string /direct /no-wait /lines /part size
/with end-of-line /mode args /custom params /skip length
DESCRIPTION:
Reads from a file, url, or port-spec (block or object).
READ is a native value.
ARGUMENTS:
source -- (Type: file url object block)
REFINEMENTS:
/binary -- Preserves contents exactly.
You didn't say what type of files could be in the directory, so binary
would be safer.
There would need to be a fuller description of what the directory
could contain I think. If just files, then no problems, but if
directories too, then you'd have to say what to do with them. They
could be required to be ignored, copied if they're chosen as the
random choice, or looked through too if the files within them are to
be part of the random choice.
> I think that this can be graded for "effort" by measuring the number
> of steps in the algorithm (5) by the number of actions taken in the
<<quoted lines omitted: 19>>
> other solutions available and see for themselves who is better and
> who isn't.
--
Carl Read
[31/32] from: edanaii:cox at: 10-Nov-2002 9:08
Carl Read wrote:
>On 10-Nov-02, Ed Dana wrote:
>>Second, as part of my algorithm, I had specified a Source and Target
<<quoted lines omitted: 6>>
>was a bit ambiguious I thought, and I chose file, but I can see how
>Target could be either, and my attempt just assumes it's a file.
Well, it was clear in my head. :)
True, the problem with algorithms is that they need to be specified
clearly, and what's clear to one is not always clear to another. But
then, that's what code reviews are for. :) And why any submissions
should be reviewed before being accepted.
>>Also, you chose to Write the file as a binary file. Is this safer?
>>Or just focused on binary? Just wondering...
>>
>>
>
>If you don't specify binary, it's possible the file could be
>changed...
>
Hmmm... Thinking....
This is more technical than specification oriented, so... Review
process, again.
>>>? read
>>>
<<quoted lines omitted: 17>>
>random choice, or looked through too if the files within them are to
>be part of the random choice.
Definately, your choice of binary was the better choice. I didn't weigh
that issue. So the final version should include binary.
My feeling would be, if it ain't specified, then don't do it. It should
meet the algorithm, as specified. If the algorithm is missing something,
then the algorithm needs to be revised.
--
Sincerely, | Tell me, tell me, where I'm going; I don't know
Ed Dana | where I've been. Tell me, tell me. Oh won't you
Software Developer | tell me, and then tell me again! My body's aching,
1Ghz Athlon Amiga | my heart is breaking and I don't know where to go!
| So tell me, tell me, why don't you tell me? I just
| gotta know! - Styx, Crystal Ball
[32/32] from: edanaii:cox at: 10-Nov-2002 10:25
Oops. This occured to me after I sent you my first response.
Since I was suggesting the spec should be revised (and since it's mine)
I guess I should revise it.
Bear in mind the original spec was written quickly, to illustrate a point.
So, new spec, based on your feedback:
======================================================================
RandomCopy
* Objective:
Copy a file from the source directory specified to the target
directory or file.
* Inputs
-> Source File/Directory.
If Directory, choose from all files in that directory.
If File, assume the name should be matched to the source directory and
return only the files
matching that pattern.
-> Target File/Directory.
If Directory, copy the File over without changing it's name,
If File, then change the name of the File chosen to the name of the
Target file.
* Outputs
-> Target File, as specified above.
* Procedure
1 Get all the files in the Source Directory.
2 Choose one file randomly.
3 Copy it to the Target File or Directory.
======================================================================
Recursion is still not specified, as I see no advantage to using it in
this context. I could be convinced otherwise.
Also, you'll notice I added a few things (like pattern matching) that
were not in the original spec. This was more because I hadn't yet
figured out how to do that in Java or REBOL, than because it didn't need
to be in the spec.
If any of you REBOL gurus wanna show me how, I'll gladly listen. :)
--
Sincerely, | Tell me, tell me, where I'm going; I don't know
Ed Dana | where I've been. Tell me, tell me. Oh won't you
Software Developer | tell me, and then tell me again! My body's aching,
1Ghz Athlon Amiga | my heart is breaking and I don't know where to go!
| So tell me, tell me, why don't you tell me? I just
| gotta know! - Styx, Crystal Ball
Notes
- Quoted lines have been omitted from some messages.
View the message alone to see the lines that have been omitted