nimforum mirror - Functional go vs nimrod, syntax and performance

cwds420 (orginal) [2014-01-15T01:08:14+01:00] view original

As an exercise to compare these two languages, I ported over one of go's examples from http://golang.org/doc/codewalk/functions. This code was written to use a fair bit of the available functional syntax. The original go code can also be found in go's git tree, under doc/codewalk/pig.go. The point of this post is to discuss some syntax differences which are easier explained with an example.

Ported pig.nim is as follows

# 'pig.go' from golang distribution, 'doc/codewalk/pig.go'
# Nimrod port by cwds420.  Original header:

# Copyright 2011 The Go Authors. All rights reserved.
# Use of this source code is governed by a BSD-style
# license that can be found in the LICENSE file.

import math, strutils

const
  win            = 100  # The winning score in a game of Pig
  gamesPerSeries = 10    # The number of games per series to simulate

# A score includes scores accumulated in previous turns for each player,
# as well as the points scored by the current player in this turn.
type TScore*  = tuple[player, opponent, thisTurn: int]

# An action transitions stochastically to a resulting score.
type TAction* = proc(current:TScore):tuple[result:TScore, turnIsOver:bool]

# roll returns the (result, turnIsOver) outcome of simulating a die roll.
# If the roll value is 1, then thisTurn score is abandoned, and the players'
# roles swap.  Otherwise, the roll value is added to thisTurn.
proc roll(s:TScore): tuple[result:TScore, turnIsOver:bool] =
  var outcome = math.random(6) + 1 # A random int in [1,6]
  return
    if outcome == 1:
      ((s.opponent, s.player, 0), true)
    else:
      ((s.player, s.opponent, outcome + s.thisTurn), false)

# stay returns the (result, turnIsOver) outcome of staying.
# thisTurn score is added to the player's score, and the players' roles swap.
proc stay(s:TScore): tuple[result:TScore, turnIsOver:bool] =
  return ((s.opponent, s.player + s.thisTurn, 0), true)

# A strategy chooses an action for any given score.
type TStrategy = proc(score:TScore): TAction

# stayAtK returns a strategy that rolls until thisTurn is at least k, then
# stays.
proc stayAtK(k:int): TStrategy =
  return
    proc(s:TScore):TAction =
      return
        if s.thisTurn >= k:
          stay
        else:
          roll

# play simulates a Pig game and returns the winner (0 or 1).
proc play(strategy0, strategy1: TStrategy): int =
  var strategies = [strategy0, strategy1]
  var s: TScore
  var currentPlayer = math.random(2) # Randomly decide who plays first
  while s.player + s.thisTurn < win:
    var action = strategies[currentPlayer](s)
    let (sResult, turnIsOver) = action(s)
    s = sResult
    if turnIsOver:
      currentPlayer = (currentPlayer + 1) mod 2
  return currentPlayer

# roundRobin simulates a series of games between every pair of strategies.
proc roundRobin*(strategies: openarray[TStrategy]):
      tuple[wins:seq[int], gamesPerStrategy:int] =
  result.wins = newSeq[int](len(strategies))
  for i in low(strategies) .. high(strategies):
    for j in i+1 .. high(strategies):
      for k in 0 .. <gamesPerSeries:
        var winner = play(strategies[i], strategies[j])
        if winner == 0:
          inc result.wins[i]
        else:
          inc result.wins[j]
  result.gamesPerStrategy = gamesPerSeries * (len(strategies) - 1) # no self play
  return result

# ratioString takes a list of integer values and returns a string that lists
# each value and its percentage of the sum of all values.
# e.g., ratios(1,2,3) = "1/6 (16.7%), 2/6(33.3%), 3/6 (50.0%)"
proc ratioString(vals:varargs[int]):string =
  var total = 0
  for val in vals:
    total += val
  result = ""
  for val in vals:
    if result != "":
      result &= ", "
    var pct = 100 * val / total
    result.add( align($val,3) & "/" & align($total,3) &
                "(" & align(formatFloat(pct, ffDecimal, 1),4) & "%)" )

when isMainModule:
  #math.randomize()
  var strategies:array[win, TStrategy]
  for k in low(strategies) .. high(strategies):
    strategies[k] = stayAtK(k+1)
  var (wins, games) = roundRobin(strategies)
  for k in low(strategies) .. high(strategies):
    echo "Wins, losses staying at k=", align($(k+1),4), ": ",
          ratioString(wins[k], games-wins[k])

The performance of this example is notable, as the code was lifted and pretty much translated as is from go's site:


Performance results (2013 2.3 GHz i7 Macbook Pro OSX 10.9.1):

go version go1.2 darwin/amd64
Nimrod Compiler Version 0.9.3 (2014-01-07) [MacOSX: amd64]  (release branch)

time go build pig.go
time nimrod c --verbosity:0 pig.nim
time nimrod c --verbosity:0 -d:release pig.nim
time ./pig

runs done 5 times and averaged
                                 
                                 gamesPerSeries constant
                 | compile  |  run-10  | run-100 | run-1000 |
==============================================================
go               |  0.182s  |  0.368s  |  3.585s |  35.765s |
nimrod debug     |  0.293s  |  0.744s  |  7.316s |  73.139s |
nimrod release   |  0.338s  |  0.223s  |  2.158s |  21.461s |

Note that the nimrod version performs significantly better than go does on this functional code (their own example), even though released Go is now 2 years old, is on version 1.2, and has a full time staff dedicated to it. The go version is 2.0Meg and the nimrod version is 41K (partly because go includes stdlib, nimrod links to it as does every other c program). Nimrod is doing very well; it's impressive what you have put together.

A few minor items stand out when looking at the two versions. Note that as is nimrod as it stands today is perfectly usable; the pig sample works great and there are a minimum of syntax anomalies to work around. As nimrod has not yet reached version 1.0, it appears there is still time to discuss these things:

The openarray keyword seems extraneous. It appears that the only function it serves is to indicate to a procedure that an array argument has a variable (not fixed) size, starting at index 0. Perhaps the openarray keyword could be folded into the array keyword, so you have something like proc roundRobin(strategies: array[ ,TStrategy]) on line 65.

I gather that the ideomatic nimrod way to return multiple values is through tuples, which was done in this example. The syntax of that could be simplified so you don't need the tuple[] on the return type, just ( ). For example, line 24 could read proc roll(s:TScore): (result:TScore, turnIsOver:bool) or even just proc roll(s:TScore): (TScore, bool) if the subsequent assignment to result was done against a tuple type. Then you could advertise you support multiple return types (which for all intents and purposes you do today).

Currently unpacking the returned tuple from such a procedure needs to be done against a var or a let, so the code from line 58 through 60 isn't as terse as it could be. It would be nice to assign an unpacked tuple to previously defined var's. I suspect there's a pretty good reason why this is, and it's already on the "do that someday" list somewhere.

The string formatting provided by the current nimrod standard library certainly works, and one can format something the same way you would in a standard printf type routine. The syntax on line 91 and 101 is awkward though; I see another user at https://gist.github.com/ddlsmurf/887776 kept an imported C version of printf around for their work through their online cheat-sheet. I think nimrod in it's current form cannot support arbitrary varargs; varargs have to be all the same type and as such one cannot write a general purpose printf type function. Once again, I suspect there's a really good reason for this and it's already on the list of something to do someday.

go's vararg syntax is more concise and to the point as that in the nimrod code. For instance, line 82 could be proc ratioString(vals: ...int):string

The * symbol to indicate an export. * is often associated with a pointer, and it's meaning as an operator or multiplication symbol is at odds with the notion of 'export a symbol'. Go's Uppercase convention is one way given the coding convention is in flux (but that doesn't mesh well with non-latin languages); unicode is another way, perhaps § or something else readable? Possibly 2014 is the year to introduce a non-ascii character into a programming language?

At the risk of getting very nitpicky, a for statement against a array/sequence type doesn't seem to have a good way of just iterating over the indexes. You can iterate over the objects, the indexes plus the objects, but not just the indexes as this example requires. Go achieves this by using a _ in place of a variable to throw the result away. Here I suppose you could assign it to a variable then not use it, but I thought doing so would induce an unnecessary copy.

The intent isn't to introduce more work onto the current development team. From a first pass through the current nimrod compiler, it seems as though several of these items are pretty straight forward and the codebase is well put together. If this discussion thread proceeds to the point where it is thought some of these things would be nice to have, they could be implemented and submitted as a pull request as an exercise to come up to speed on how the nimrod compiler works. There's a fair bit of discussion on my end on rolling nimrod into a few upcoming projects; it seemed better to raise these minor points now while they are fresh in our minds.

filwit (orginal) [2014-01-15T02:07:53+01:00] view original

hi cwds420, good comparison, thanks for the port. I haven't gone through all the code or fully looked at you suggestions yet (don't have time right now), but might I suggest also compiling with clang (--cc:clang) for comparison. It should drop the compile-times down a bit, and I'm interested to know how much. The latest LLVM 3.4 seems to compile significantly faster for me, but I haven't done extensive measurements.

renoX (orginal) [2014-01-15T09:56:24+01:00] view original

I'm always suspicious of benchmark which include 'random' function: there can be a lot of difference between the performance of the random function in libraries depending on the tradeoff used: for your benchmark to be meaningful, use your own random function on Go and Rust not the library one.

zahary (orginal) [2014-01-15T11:02:36+01:00] view original

Heterogeneous generic varargs and tuple unpacking into variables are indeed on the roadmap.

The special short-hand syntax for tuple return values is interesting idea, but you should always be careful when making proposal for specialized syntax. Nimrod allows you to have an arbitrary expressions in any place where a type is expected (you can expand a template or macro, using arbitrary operators) and you should always look at the problem by asking "what kind of expression is that?". In that light, (TScore, bool) would be a tuple of two typedescs and indeed, it may be reasonable to treat that as an indication that a tuple will be returned by the proc.

Regarding iterating over the indexes of a collection, here is some working code:

iterator indices(c): int =
  for i in low(c)..high(c):
    yield i

var s = @[1, 2, 3]

for i in s.indices:
  echo i

Araq (orginal) [2014-01-15T14:16:44+01:00] view original

Heterogeneous generic varargs are already supported in 2 ways: varargs[T, op] aka "local type converter" or use a macro. You can also easily have ...int expand to varargs[int] via a template.

The * as export marker is not open for discussions, sorry. Using Uppercase to export things is stupid. This means you need to rename the identifier everywhere just to export it. Not a big deal especially with IDE support, but still stupid.

openarray also can take a seq and so I think it's a good idea to not conflate it with array.

A shortcut for tuples is indeed planned.

BTW Go doesn't support assert because of some absurd religious beliefs ("can be abused"), Nimrod's assert is implemented in the stdlib without compiler support. That's the real difference.

cwds420 (orginal) [2014-01-16T03:48:34+01:00] view original

Replacing the rand calls with a simple 'n-1' return shows that all that this code is really benchmarking is the call to rand(). The complicated go rand() implementation is the sole reason for the difference. The no-rand 'n-1' version on my machine results in the nimrod code being twice as slow (with no attempts at optimization beyond the -d:release flag), but both are so fast to make the results pretty meaningless - much like the compile times.

Either putting a '*' on the end or changing the leading case seems like a pretty similar amount of effort, and is just a naming convention - no right answer; just pick something (which you did). Both both are far better than header files for exports. Personally I'm glad someone finally stopped using & and * as prefixes for address and pointer notation; 'ref' and 'ptr' are far easier to read. Decoding too many obscure C * and & laden statements from someone attempting to be clever explains my own bias against the '*' symbol used for anything other than multiplication.

Will have to try out the pre-existing varargs support and perhaps put together a printf-like function as it would be mostly library glue, unless someone else has already done this.

Didn't know that openarrays could take a sequence; but indeed that's mentioned in the docs as "In addition to arrays sequences can also be passed to an open array parameter". Need to be a more careful reader.

Had not heard about the Go folks bias against assert, though it's not that surprising. I figured they compiled in their own Plan9 stdlib as much as anything to give it (and their C compiler) a new lease on life.

For nimrod features, it would be useful to have some insight on what is planned, and a very rough idea of when it may arrive both to assist in knowing what parts of the language are in flux, and to know what can be used today and what may be available to be used in the future. I haven't came across much in the way of forward looking statements or lists in the publicly available docs. Such a list can help sell the language to others who stop by for a casual look.

Mirror of forum.nim-lang.org

345 :: Functional go vs nimrod, syntax and performance