Sum of 1 to 1000000000 in different programming languages • Hacker News Board

Re: Sum of 1 to 1000000000 in different programming languages

#61

Post by hannibal5 » Mon, Aug 05, 2013, 8:53 PM UTC

hannibal5 wrote: post #58

Common Lisp: * (loop for i from 1 to 1000000000 sum i) 500000000500000000 *

;; let's time it * (time (loop for i from 1 to 1000000000 sum i))

  Evaluation took:
    2.374 seconds of real time
    2.372148 seconds of total run time (2.372148 user, 0.000000 system)
    99.92% CPU
    8,071,475,337 processor cycles
    0 bytes consed
  
  500000000500000000


  * (disassemble (lambda () (loop for i from 1 to 1000000000 sum i)))

  ; disassembly for (LAMBDA ())
  ; 02C21574:       BB02000000       MOV EBX,   2                 ; no-arg-parsing entry point
  ;       79:       31C9             XOR ECX, ECX
  ;       7B:       EB27             JMP L1
  ;       7D:       90               NOP
  ;       7E:       90               NOP
  ;       7F:       90               NOP
  ;       80: L0:   48895DF8         MOV [RBP-8], RBX
  ;       84:       488BD1           MOV RDX, RCX
  ;       87:       488BFB           MOV RDI, RBX
  ;       8A:       4C8D1C25E0010020 LEA R11,  [#x200001E0]      ; GENERIC-+
  ;       92:       41FFD3           CALL R11
  ;       95:       480F42E3         CMOVB RSP, RBX
  ;       99:       488BCA           MOV RCX, RDX
  ;       9C:       488B5DF8         MOV RBX, [RBP-8]
  ;       A0:       4883C302         ADD RBX, 2
  ;       A4: L1:   483B1D25000000   CMP RBX, [RIP+37]
  ;       AB:       7ED3             JLE L0
  ;       AD:       488BD1           MOV RDX, RCX
  ;       B0:       488BE5           MOV RSP, RBP
  ;       B3:       F8               CLC
  ;       B4:       5D               POP RBP
  ;       B5:       C3               RET
  ;       B6:       CC0A             BREAK 10  ; error trap
  ;       B8:       02               BYTE #X02
  ;       B9:       18               BYTE #X18                  ; INVALID-ARG-COUNT-ERROR
  ;       BA:       54               BYTE  #X54                  ; RCX
  ;       BB:       90               NOP
  ;       BC:       90               NOP
  ;       BD:       90               NOP
  ;       BE:       90               NOP
  ;       BF:       90               NOP
  ;       C0:       90               NOP
  ;       C1:       90               NOP
  ;       C2:       90               NOP
  ;       C3:       90               NOP
  ;       C4:       90               NOP
  ;       C5:       90               NOP
  ;       C6:       90               NOP
  ;       C7:       90               NOP
  ;       C8:       90               NOP
  ;       C9:       90               NOP
  ;       CA:       90               NOP
  ;       CB:       0000             ADD [RAX], AL
  ;       CD:       0000             ADD [RAX], AL
  ;       CF:       0000             ADD [RAX], AL
  ;       D1:       94               XCHG EAX, ESP
  ;       D2:       3577000000       XOR EAX, 119
  ;       D7:       0000             ADD [RAX], AL
  NIL

Re: Sum of 1 to 1000000000 in different programming languages

#62

Post by robomartin » Mon, Aug 05, 2013, 9:07 PM UTC

robomartin wrote: post #18

APL: +/⍳1E9 Try it yourself, download NARS2000 (free) here: http://www.nars2000.org/ The "⍳" character is entered by typing ALT+i Explanation: 1E9 is 1,000,000,000 ⍳1E9 generates a vector containing integers from 1 to 1,000,000,000 (inclusive) +/ is the sum of the vector Any good APL interpreter will not actually generate a vector with a billion numbers but rather recognize the above expression and optimize the resul…

Seeing that some are adding timings to the posted solutions.

The APL solution I posted above (+/⍳1E9) takes 56 microseconds to execute on my system (checked by solving it 100,000 times in a loop).

The interpreter is obviously not doing a huge memory and clock-cycle sucking expansion of a one billion element vector.

This highlights another advantage of a symbolic language: Idioms or patterns within code can be recognized replaced with equivalent highly-efficient, highly-tuned operations. The above example is obviously solved by having the interpreter swap it out for the well-understood mathematical solution.

Because of this the programmer can focus on the problem space rather than having to dork around with figuring out optimizations. Granted, this is a simple one for anyone with a decent math background, but it can get far more complex. Have a look at the famous Finn APL idiom library:

http://aplwiki.com/FinnAplIdiomLibrary

An interpreter designer might very well decide to detect a good number of these idioms and execute highly tuned code instead of the memory and CPU-cycle hogging expansions that might result from running the actual code as written.

In many ways I equate this to what happens when using a language like Verilog to design FPGA circuits. You are designing hardware, not software. FPGA compilers have inference engines that recognize certain structures to mean specific circuit constructs. It's a contract. We agree that when I write this I mean to ask that you instantiate that and everyone is happy.

Re: Sum of 1 to 1000000000 in different programming languages

#63

Post by akurilin » Mon, Aug 05, 2013, 9:15 PM UTC

michaelochurch wrote: post #29

Clojure: (reduce + (range 1000000001)) Written that way, though, it takes a long time (108 sec, compared to 2.6 sec in C). So that's not fast, as elegant as it may be. This is what I have for C. It's probably not great C code. int main() { long res = 0; int i; for (i = 0; i Faster than (naive?) C is this Clojure loop (no range object). user=> (time (loop [i 0 res 0] (if (> i 1000000000) res (recur (inc i) (+ res i)))…

Do you know of any good guides for how to fine-tune Clojure in situations where you need to trade elegance for performance?

What you did that is great, so I'm wondering where I'd be able to find out more about such techniques.

Re: Sum of 1 to 1000000000 in different programming languages

#64

Post by waterhouse » Mon, Aug 05, 2013, 9:29 PM UTC

gshubert17 wrote: post #46

SBCL: Commenter postfuturist said that this code: (time (let ((sum 0)) (loop :for x :from 1 :to 1000000000 :do (incf sum x)) sum)) took about 3 seconds from his REPL with SBCL, with about 8.5 billion CPU cycles and 0 bytes consed. Does anyone know why the same code on my version of SBCL (1.0.55.0-abb03f9) on a Mac took 156 billion cycles and consed 24 billion bytes?

Consing sounds like it's allocating bignums. My guess is that you're using a 32-bit build of SBCL. In that case, fixnums only go up to something like 2^30, and arithmetic with larger numbers will allocate memory. Can you check?

  * (log most-positive-fixnum 2) ;on 64-bit
  
  62.0

Re: Sum of 1 to 1000000000 in different programming languages

#65

Post by tsahyt » Mon, Aug 05, 2013, 9:34 PM UTC

dons wrote: post #24

tsahyt wrote: post #10

Haskell foldl' (+) 0 [1..1000000000] You could use sum, but that will eat up a lot of RAM because of the laziness. EDIT: For the fun of it, I decided to do the same in a slightly more esoteric language, so here's a Prolog version (given that your stack is big enough) rangesum(0,0). rangesum(N,X) :- M is N - 1, rangesum(M,Y), X is Y + N. ?- rangesum(1000000000, X), write(X).

sum is fine in GHC. It is specialised for Integer. GHCi uses naive sum though.

Good to know that. I was trying that code in GHCi, which explains a few things now.

Re: Sum of 1 to 1000000000 in different programming languages

#66

Post by pbsd » Mon, Aug 05, 2013, 9:38 PM UTC

Aardwolf wrote: post #25

Someone replied the following in there: "The key in this case is using C99's long long data type. It provides the biggest primitive storage C can manage (128-bits on 32-bit machines and 256-bits on a 64-bit machine) and it runs really, really fast." Isn't long long "typically" 64-bit? (I know the C standard doesn't actually specify any actual size). What platform does this long long type really give you the full 128…

Per the C99 standard, long long is guaranteed to be at least 64 bits, but is allowed to be larger.

Re: Sum of 1 to 1000000000 in different programming languages

#67

Post by michaelochurch » Mon, Aug 05, 2013, 9:48 PM UTC

akurilin wrote: post #63

michaelochurch wrote: post #29

Clojure: (reduce + (range 1000000001)) Written that way, though, it takes a long time (108 sec, compared to 2.6 sec in C). So that's not fast, as elegant as it may be. This is what I have for C. It's probably not great C code. int main() { long res = 0; int i; for (i = 0; i Faster than (naive?) C is this Clojure loop (no range object). user=> (time (loop [i 0 res 0] (if (> i 1000000000) res (recur (inc i) (+ res i)))…

Do you know of any good guides for how to fine-tune Clojure in situations where you need to trade elegance for performance? What you did that is great, so I'm wondering where I'd be able to find out more about such techniques.

I don't. I'm far from an expert on high-performance Clojure. (I'm really glad that there is such a thing, and that people focus on it, however.) Joy of Clojure and Programming Clojure get into optimizations a little bit, but I think that field is still fairly new.

Sometimes with seqs one can end up with a "holding head" problem; if you're doing stream processing but holding on to a seq, you can end up having the whole thing in memory, which would kill you. That's not what's happening there, though; a default-configured JVM can't hold anything close to a billion longs in memory.

One of the neat things is that, because the REPL actually compiles code (there's no interpreter) you get the same performance with the time macro as you would get in compiled code. What that means is that testing for performance can be done at the REPL and quickly.

To explain what I did and why, I figured that the tight loop would be optimized to Java-like performance. With the more elegant formulation, I didn't know what was going on in terms of types (how is +, a vari-aritied function with many type signatures, being handled)? If the loop performed poorly, I'd probably have put type hints on the arguments and replaced + with unchecked-add; but it performed well so I left it as it was.

Re: Sum of 1 to 1000000000 in different programming languages

#68

Post by j-b » Mon, Aug 05, 2013, 9:48 PM UTC

Visual LANSA:

  begin_loop using(#int8) to(1000000000)
    #r_dvp += #int8
  end_loop

From which VL will then generate 2,050 lines of C++.

Re: Sum of 1 to 1000000000 in different programming languages

#69

Post by gshubert17 » Mon, Aug 05, 2013, 9:59 PM UTC

waterhouse wrote: post #64

gshubert17 wrote: post #46

SBCL: Commenter postfuturist said that this code: (time (let ((sum 0)) (loop :for x :from 1 :to 1000000000 :do (incf sum x)) sum)) took about 3 seconds from his REPL with SBCL, with about 8.5 billion CPU cycles and 0 bytes consed. Does anyone know why the same code on my version of SBCL (1.0.55.0-abb03f9) on a Mac took 156 billion cycles and consed 24 billion bytes?

Consing sounds like it's allocating bignums. My guess is that you're using a 32-bit build of SBCL. In that case, fixnums only go up to something like 2^30, and arithmetic with larger numbers will allocate memory. Can you check? * (log most-positive-fixnum 2) ;on 64-bit 62.0

You're right. I have a 32-bit build, since I get:

* (log most-positive-fixnum 2) 29.0

Thanks.

Re: Sum of 1 to 1000000000 in different programming languages

#70

Post by radiospiel » Mon, Aug 05, 2013, 10:15 PM UTC

pc86 wrote: post #28

ck2 wrote: post #22

Knowing how to use a language is critical to get expected results. This gives the proper result in PHP by forcing the integer cast. $sum = (int) $sum + $i;

It's been a long time since I've worked with PHP, I assume $sum += (int) $i; will still convert to float once the size of $sum gets to the requisite size?

One of the reasons to stay away from PHP. Requesting and int but getting a float regardless? That doesn't sit well w/me.