Lemme rephrase this rather interesting problem: There are 2055 startups, 2006 bigcorps & 2017 zombies. If the startup gets bought out by the bigcorp, the bigcorp has wasted its well earned money and soon becomes a zombie. If the zombie folks instead join hands with the startup, they suddenly make pots of money & the startup become a bigcorp. Finally, if the bigcorp uses its cash prudently and buys the zombie, it starts innovating & becomes a startup.

So the claim is that if you let this economy play out in all its glory, there will be 1.448 billion buyouts. To arrive at this giant figure of 1,448,575,636 takes anywhere between 335 seconds for the C++ hacker to 7000 seconds for the JS guys.

Now give it your best shot!

1) In any of the transformations [(-,-,+),(-,+,-),(+,-,-)], the delta b/w numbers (s-b, s-z, b-z) changes by 0 or 2. What this tells us is that if the delta is odd to start, it will always be odd, if even always even.

2) Since the final state will involve only one type left standing (or else the stronger could eat the weaker), we know that the final counts will be two at 0, one at something >0. Since our losers end with an even delta (0), they must always have had an even delta. In the scenario you proposed, that's s and z (2055 - 2017 = 38). So b, bigcorps, is going to be our winner.

3) Now that we know who will win, we need to find the maximum possible number of bs remaining. Since each move reduces the total population by one, the maximum bs will be produced by the shortest sequence of moves that gets rid of all zs and ss.

4) As long as z>0 and s>0, our best move is to have z eat s, as it drops the population of z and s by 2. So our first sequence is to have all zs eat ss, leaving us with s = 38, b = 4023, z = 0.

5) When z = 0, our only possible move is b eats s, creating a z, which can then be eaten by an s to produce a b, thereby restoring b to its original count and lowering s by 2. After repeating this sequence 19 times to get rid of the 38 ss, we'll have s = 0, b = 4023, z = 0.

Ergo, maximal final state is 4023 bigcorps.

I made some modifications (diverging further from the "functional" nature, if you could call it that) and as you can see it is much faster[0].

Output:

  $ node new-magicForest.js 2017 2055 2006
  total forests: 6128
  { goats: 0, wolves: 0, lions: 4023 }
  total time: 20ms

I summarize the author's algorithm as follows: take an array of R^3 vectors, and for each element in the vector, perform the [+,-,-], [-,+,-], and [-,-,+] transform. So N numbers become 3N numbers, which is followed by a duplicate removal process faciliated by the sorting.

The improvement is that the duplicate removal can be accomplished without sorting.

Let's say you have an array of R^3 already sorted. Then say you create 3 arrays each of which is created by "shifting" the array in each of the 3 directions. Call the original A, and the derived B0, B1, B2. Note that B0, B1, and B2 are each sorted since element within each array is adjusted in the same direction. Then all you need to do is to do a 3-way merge, which takes linear time.

I bet by doing this, the runtime could be significantly reduced. My guess is that it runs in the range of 10-30 seconds (instead of 335 seconds).

A minor nit to pick: the 1,448,575,636 number is not the number of buyouts. (It looks like the number of nodes in the evaluation graph.)

Spoiler: the answer is 111110110111_2. (edit: had the wrong answer)

1. CPUs have gotten very good at doing runtime optimization kinds of things on their own, like predicting branches and reducing the cost of virtual function calls. 2. Java only does optimizations that can be done quickly, since the optimizer has to compete with the executing program itself. 3. The claim was overblown to begin with, and Java is trying to do too many other things, like be secure, that interfere with performance.

They use Java because it's fast enough, easy, safe, reliable, easy to instrument, easy to debug, has wonderful tool support, is mature, has many tested and heavily used frameworks, has a free chunk of code to do anything you can imagine you can just snag via maven, integrates with everything, works on all major platforms and costs nothing.

That makes it fast in other ways.

Writing really cache friendly code in Java requires to look at the problem orthogonally and use int[]/long[] instead of a small Object with 3 small ints.

The Java version simply features some quite horrific code but can easily be run in parallel - no one mentions that. Using streams in pure functional way w/o the parallel in mind is a ritual suicide.

Finally, The CPU running benchmark has only 2 cores which is a disadvantage with tons of allocation and garbage.

Converting Object[] arrays into single chunks of packed members when they're all the same type would be a pretty big win by itself.

1) You wrote that code in BOTH Java and C++, optimized both, and compared their running times.

2) Said code was CPU bound. For heavy IO bound code you could even use TCL and get "fractional" differences.

See http://benchmarksgame.alioth.debian.org/u64q/performance.php...

In terms of raw CPU speed, access to vector instructions directly can be game changer in various applications. Also C/C++ compilers are also getting better each day.

That is a very good observation. Looking at back in the past at some point memory speed wasn't that much slower than CPU speed (rather because CPU speeds were not that fast then).

So then throwing more memory at something seems like a very good way improve performance. Like say following long chains of pointers through some nested structure or long linked list was ok. At some point CPU speed went through the roof and left memory access speeds behinds.

So then caches became very important. Cache aware programming was a "thing".

That, coupled with lots having virtualized/cloud machines everywhere that have limited memory kind of turned that initial thinking on its head. Small memory footprint became a desirable trait. Just like in the old MS-DOS & Turbo Pascal days.

Java sort of flourished and grew in that time period where "throw more ram at it to get performance" was a very obvious thing to do. Now I think it is less obvious that is the best way.

(And perhaps Java's current or future GC and JIT strategies will start to take into account caches and memory frugality better).

Now that said I am still amazed at how it can achieve such great performance given all the stuff it does behind the scenes. It is not faster than C but heck, it is very fast still.

Also, the JVM JIT needs a steady-state workload to make good guesses about it's optimizations - if it JITs a bunch of methods and then the load changes such that the optimizations no longer apply (loops iterate differently, inlined methods don't get called as much), the JVM's runtime optimization can be foiled. JITting a very heterogenous program can trick the JVM into finding a local-minimum in native performance (which I guess is still a lot better than actually interpreting java byte code).

I mean, Fortran did worse than Java. Where is your writeup for that?

http://www.artima.com/designtechniques/hotspotP.html

"According to Sun Microsystems, the Hotspot virtual machine, Sun's next-generation Java virtual machine (JVM), promises to make Java "as fast as C++.""

There's not a lot of wiggle room there.

There are plenty of serious, technically deep people trying to convince their colleagues that Java is as fast as C.

Such persons are quite annoying as they try to influence a lot of students.

You'll note that the FORTRAN native code is indeed beaten by Java.

1. Fortran's compilers haven't advanced at the same rate as other languages due to its lack of popularity.

2. Fortran is inherently harder to optimize.

3. People have forgotten how to write fast Fortran, since no one uses it anymore.

I don't know which it might be.

Fortran compilers have been making quite some progress (particularly ifort, but gfortran isn't bad recently).

And due to the way multidimentional arrays are built into the language, aliasing isn't nearly as much of an issue for aggressive optimizations.

  next_forests.reserve(forests.size() * possible_meals.size());

I'm instead shocked that the C++ version beat Fortran.

  ./magic_forest_gcc 617 655 606  7.22s user 0.36s system 100% cpu 7.580 total
  ./magic_forest_icc 617 655 606  7.00s user 0.34s system 100% cpu 7.340 total
  ./magic_forest_clang 617 655 606  5.73s user 0.25s system 100% cpu 5.980 total

  gcc version 4.8.2
  icc version 14.0.1
  clang version 3.4
  (On 3.14 powered arch linux)

Having said that, most of ICC's general gains over GCC and LLVM are due to the much faster maths libraries (even more so on Linux), and that doesn't look like that would be useful for these tests...

  clang 29K
  gcc 36K
  icc 89K

Using sort to filter duplicates is horribly worse compared to hashing (javascript for instance). Java version has rather poor impl, it's interesting to see the GC+allocation cost and the GC type used. C++ version does not use really use func. prog in find_stable_forests and meal...

Is this really true? A sort plus a linear scan has very low constant time factors, good cache locality (depending on the sorting algorithm used), and no need to allocate if you're sorting in place. I've seen good results using sort to filter duplicates in my own performance-sensitive code. Are you saying this technique is "horribly worse" based on your experience or intuition?

http://stackoverflow.com/questions/11227809/why-is-processin...

It will likely get faster the more duplicates you have, as it allows the CPU to predict a branch more reliably several times before being wrong and having to re-do some of its prediction stuff. (note that I'm not experienced with optimizing stuff, dealing with cache optimizations, etc., but I have read a decent amount, and I did take a class about CPU architecture) I would also suspect that hashing might end up messing with memory all over the place, causing the cache to be partly useless.

For non-hot code, it is perfectly fine, but in this case, inside of a main loop like this it is a waste of cpu cyles. Compare the amount of forests here:

   $ node orig-magicForest.js 117 155 106
   total forests: 1522899
   { goats: 0, wolves: 0, lions: 223 }
   total time: 816ms

   $ node new-magicForest.js 117 155 106
   total forests: 428
   { goats: 0, wolves: 0, lions: 223 }
   total time: 6ms

  Goats Wolves Lions    C++11  Nimrod
     17     55     6     0.00    0.00
    117    155   106     0.17    0.01
    217    255   206     0.75    0.01
    317    355   306     2.16    0.01
    417    455   406     5.28    0.01
    517    555   506    10.75    0.01
    617    655   606    19.15    0.02
    717    755   706    31.58    0.02
    817    855   806    46.52    0.02
    917    955   906    67.94    0.02
   1017   1055  1006    93.75    0.02
   2017   2055  2006   731.42    0.04

  Goats Wolves Lions    C++11  Nimrod
     17     55     6     0.00    0.03
    117    155   106     0.17    0.13
    217    255   206     0.75    0.62
    317    355   306     2.16    1.89
    417    455   406     5.28    4.34
    517    555   506    10.75    8.42
    617    655   606    19.15   14.45
    717    755   706    31.58   23.04
    817    855   806    46.52   33.69
    917    955   906    67.94   48.57
   1017   1055  1006    93.75   65.25
   2017   2055  2006   731.42  500.95

   Meal[forests_] := 
     Outer[Plus, forests, Permutations[{1, -1, -1}], 1] // Catenate // 
       DeleteDuplicates // Select[AllTrue[NonNegative]];

I'm not sure if I got the problem right, because it solves the hardest case almost instantly (2006 lions, 2055 wolves, 2017 goats -> 4023 lions), in 0.8s on my macbook air.

I used a general search algo that I've also used in the past for the missionaries and cannibals and snake cube puzzles.

It uses a set to store the past states seen, instead of deduping a list.

   | 217 | 255 | 206 | 0.5 s (C++ 1.6s)
   | 317 | 355 | 306 | 1 s   (C++ 4.8s)
   | 617 | 655 | 606 | 3.5 s (C++ 35s)
   | 917 | 955 | 906 | 10s   (C++ 117.5)

    let actions = [|[|-1; -1; 1|]; [|-1;1;-1|]; [|1; -1;-1|]|]

    let stable [| g ; w; l|] = (g = 0 && (w = 0 || l = 0)) || (w = 0 && l = 0)

    let isSound = function | [| x ; _; _|] | [|_; x; _|] | [|_; _; x|] when x < 0 -> false | _ -> true

    let stateChange state =  Array.map (Array.map2 (+) state) actions 

    let deduplicate sequence = sequence |> Seq.groupBy hash |> Seq.map (snd >> Seq.head)

    let forest start =
      let rec search curforest =  
            let nextforest = Array.collect stateChange curforest
                                      |> Array.filter isSound 
                                      |> deduplicate 
                                      |> Seq.toArray  
                                
            if nextforest.Length = 0 then curforest 
            else match Array.tryFind stable nextforest with 
                    | Some _ -> nextforest
                    | None -> search nextforest

      search (stateChange start) |> Array.filter stable

Also, the clang C++ compiler is (a lot) slower than gnu C++ compiler. (we had a benchmark on HN that showed that clang C++ is 5% slower and asm.js is 10% slower than gnu gpp) The comparision should be executed on Linux or Windows as OS X is known for shipping with older versions of Unix tools/applications.

  import qualified Data.Set as S                                                                                                                                                
  
  data Forest = F Int Int Int
    deriving (Eq, Ord, Show)
  
  meal forests = (S.toList . S.fromList)
    [nextForest |
     forest <- forests,
     meal <- possibleMeals,
     let nextForest = forest <+> meal,
     valid nextForest]
   where
    possibleMeals = [
      F (-1) (-1)   1,
      F (-1)   1  (-1),
      F   1  (-1) (-1)]
    F x y z <+> F x' y' z' = F (x+x') (y+y') (z+z')
    valid (F x y z) = x >= 0 && y >= 0 && z >= 0
  
  findStable forest = iter [forest]
   where
    iter forests | not (done forests) = iter (meal forests)
                 | otherwise          = filter stable forests
    done forests = null forests || any stable forests
    stable (F _ 0 0) = True
    stable (F 0 _ 0) = True
    stable (F 0 0 _) = True
    stable _         = False
  
  main = print $ findStable (F 117 155 106)

In fact, the execution time is more than doubled.

Why is this so?

The Eclipse generated version of hashCode():

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + goats;
			result = prime * result + lions;
			result = prime * result + wolves;
			return result;
		}

		@Override
		public int hashCode() {
			final int magic = 0x9e3779b9;
			int seed = 0;
			seed ^= this.goats + magic + (seed << 6) + (seed >> 2);
			seed ^= this.lions + magic + (seed << 6) + (seed >> 2);
			seed ^= this.wolves + magic + (seed << 6) + (seed >> 2);
			return seed;
		}

Example:

Forest.makeForest(517, 555, 506)

With original hashCode(): 8.177 s

With Eclipse generated hashCode(): 19.237 s

(100% repeatable with only a few 100ms diff between executions)

That is, there's nothing inherent to Go, as a programming language, that makes it less functional than Java or C++. Go has first class support for functions and methods as objects, with proper closures, anonymous funcs and such.

Also performance of fortran code is quite dependent on the compiler and compiler options. Somethng that was not well described.

I may even take a stab at rewriting it myself if I get some time.

I'm a bit curious how an asm.js port (via whatever means. maybe c++ -> emscripten?) ends up performing.

edit: heh.

>Also note that FORTRAN is not included in the list [of relative speedups], because no sane person would switch to FORTRAN from another programming language voluntarily.

http://unriskinsight.blogspot.co.at/2014/05/the-f-word-of-pr...

Any real explanations?