> Here's a laundry list of why your O'Caml program in inefficient: > > 1. You use lists. Lists aren't designed to be fast (computationally) > to use. They're designed to be fast (programmatically) to use. You'll > be hard pressed to find a production, speed-sensitive Lisp or O'Caml > program that uses lists.
Okay... but here's my point: Every single example that shows how elegant Haskell and OCaml are uses lists. The 4-line Quicksort example for Haskell uses lists. All of the code that demonstrates easy reuse of functions and functions taken as arguments uses lists (like how easy it is to implement quite complicated algorithms using only map and filter, for example).
So, proponents say "Everyone should use functional languages because they can express complicated problems in elegant ways and result in cleaner, more reusable code."
But what you're saying in #1 above is that in "production," speed-sensitive code, no one is using lists... this would mean that no one is using map, filter, or any other pieces of reusable primitive code. So, they are instead all using mutable data structures... I.e., they are programming with side-effects and loops (random access instead of recursion, even when ever element of an array/list needs to be accessed/processed).
That was my point exactly. If you write elegant OCaml code using all of the lovely (and I mean lovely, really) tricks that they present when they demonstrate why OCaml is cool, you end up with code that is too slow to use in the real world.
I would say that my C++ (or most would call it C) implementation is elegant enough... easy to understand... no messy optimization tricks. Sure, I'm not using objects and templates everywhere, but these structures are hardly needed to solve this simple problem.
> 2. Practically none of your functions are written tail-recursively.
Good point.
> 2.5. You use a list append (@) inside a loop (generateStates). > List.append is O(m), where m is the length of its first argument. If > you write an implementation, you'll see why. It probably doesn't make > much of a difference here (generateStates is only called once) but it's > something to watch out for.
Of course, as you point out, generateStates has almost no effect on the running time. However, I wonder how you might implement that in an elegant way in OCaml without @. In C, I just looped over all numbers between 0 and 2^stateLength and converted the bit representations for the numbers to cell on/off states.
> 3. For Pete's sake, man, you're using an association list for your > memos! Surely you know that lookup in an association list is O(n) in > the size of the list.
I simply Googled for "memoization Ocaml" and found that code: http://www.emeraldtiger.net/modules.php?op= modload &name=News&file=article&sid=9
The author pointed out how "sweet" polymorphism is... one block of code that can be used to memoize any function. Sweet indeed, and it certainly sped up my OCaml code a lot (without memoization, it was so slow as to be intractable for anything larger than about 4x4).
So... maybe you can re-write higher-order memoization code using more efficient data structures? I would love to see that code, and I'm sure the OCaml community would benefit from having that in their toolbox.
I agree that the memoization code is probably the problem in the OCaml version. However, this code came directly from the OCaml community and was the *only* example of memoization in OCaml that I could find.
For Haskell, I used an infinite list of results that was filled in lazily as the results were needed. This also sped up the algorithm dramatically. However, I cannot get a Haskell compiler to compile itself on my platform, so I was testing all code in the Hugs interpreter, which made it too slow to be practical. Isomorphic compiled OCaml code was hundreds of times fast
I wrote the analysis. In order to analyze an interaction as complex as what happens in a BitTorrent network, you have to make some assumptions to simplify things. The "tree diagram" is not supposed to represent what actually happens in every real-world BitTorrent swarm: instead, it represent a particular case (that could happen) that maximized bandwidth usage for all nodes involved. Any other distribution structure would either: A. be equivalent in terms of distribution times, or B. not maximize bandwidth of all nodes involved.
The "all nodes have ADSL" assumption also does not change the final result: adding some T1 connections in there is not going to take you from t^2 to 2^t.
The point is this: if you don't have an explicit distribution tree of some kind, swarming does not help you. Exponential always wins out.
BitTorrent is complicated, and no other analysis of it exists (to my knowlege). If you claim that my analysis is incorrect, then you are essentially claiming that BitTorrent really has exponential distribution properties---I would love to see a new analysis that shows this.
For example you might say that the server can upload to more than one downloader at once. However, it would then be transmitting at fraction of its maximum upload rate to each downloader. You can send a chunk to 1 node in 10 seconds or 2 nodes in 20 seconds, but conservation of bandwidth prevents you from sending to 2 nodes in 10 seconds (assuming that the downloaders can saturate your upstream connection, which they most always can).
Re:I may have missed something, but...
on
P2P Meets Push
·
· Score: 1
No, the file contents is also signed. Maybe part of the documentation is confusing when it comes to this point.... please point out where so that I can fix it.
Slashdot Mirror
> Here's a laundry list of why your O'Caml program in inefficient:
>
> 1. You use lists. Lists aren't designed to be fast (computationally)
> to use. They're designed to be fast (programmatically) to use. You'll
> be hard pressed to find a production, speed-sensitive Lisp or O'Caml
> program that uses lists.
Okay... but here's my point: Every single example that shows how elegant Haskell and OCaml are uses lists. The 4-line Quicksort example for Haskell uses lists. All of the code that demonstrates easy reuse of functions and functions taken as arguments uses lists (like how easy it is to implement quite complicated algorithms using only map and filter, for example).
So, proponents say "Everyone should use functional languages because they can express complicated problems in elegant ways and result in cleaner, more reusable code."
But what you're saying in #1 above is that in "production," speed-sensitive code, no one is using lists... this would mean that no one is using map, filter, or any other pieces of reusable primitive code. So, they are instead all using mutable data structures... I.e., they are programming with side-effects and loops (random access instead of recursion, even when ever element of an array/list needs to be accessed/processed).
That was my point exactly. If you write elegant OCaml code using all of the lovely (and I mean lovely, really) tricks that they present when they demonstrate why OCaml is cool, you end up with code that is too slow to use in the real world.
I would say that my C++ (or most would call it C) implementation is elegant enough... easy to understand... no messy optimization tricks. Sure, I'm not using objects and templates everywhere, but these structures are hardly needed to solve this simple problem.
> 2. Practically none of your functions are written tail-recursively.
Good point.
> 2.5. You use a list append (@) inside a loop (generateStates).
> List.append is O(m), where m is the length of its first argument. If
> you write an implementation, you'll see why. It probably doesn't make
> much of a difference here (generateStates is only called once) but it's
> something to watch out for.
Of course, as you point out, generateStates has almost no effect on the running time. However, I wonder how you might implement that in an elegant way in OCaml without @. In C, I just looped over all numbers between 0 and 2^stateLength and converted the bit representations for the numbers to cell on/off states.
> 3. For Pete's sake, man, you're using an association list for your
> memos! Surely you know that lookup in an association list is O(n) in
> the size of the list.
I simply Googled for "memoization Ocaml" and found that code:
http://www.emeraldtiger.net/modules.php?op= modload &name=News&file=article&sid=9
The author pointed out how "sweet" polymorphism is... one block of code that can be used to memoize any function. Sweet indeed, and it certainly sped up my OCaml code a lot (without memoization, it was so slow as to be intractable for anything larger than about 4x4).
So... maybe you can re-write higher-order memoization code using more efficient data structures? I would love to see that code, and I'm sure the OCaml community would benefit from having that in their toolbox.
I agree that the memoization code is probably the problem in the OCaml version. However, this code came directly from the OCaml community and was the *only* example of memoization in OCaml that I could find.
For Haskell, I used an infinite list of results that was filled in lazily as the results were needed. This also sped up the algorithm dramatically. However, I cannot get a Haskell compiler to compile itself on my platform, so I was testing all code in the Hugs interpreter, which made it too slow to be practical. Isomorphic compiled OCaml code was hundreds of times fast
I wrote the analysis. In order to analyze an interaction as complex as what happens in a BitTorrent network, you have to make some assumptions to simplify things. The "tree diagram" is not supposed to represent what actually happens in every real-world BitTorrent swarm: instead, it represent a particular case (that could happen) that maximized bandwidth usage for all nodes involved. Any other distribution structure would either: A. be equivalent in terms of distribution times, or B. not maximize bandwidth of all nodes involved.
The "all nodes have ADSL" assumption also does not change the final result: adding some T1 connections in there is not going to take you from t^2 to 2^t.
The point is this: if you don't have an explicit distribution tree of some kind, swarming does not help you. Exponential always wins out.
BitTorrent is complicated, and no other analysis of it exists (to my knowlege). If you claim that my analysis is incorrect, then you are essentially claiming that BitTorrent really has exponential distribution properties---I would love to see a new analysis that shows this.
For example you might say that the server can upload to more than one downloader at once. However, it would then be transmitting at fraction of its maximum upload rate to each downloader. You can send a chunk to 1 node in 10 seconds or 2 nodes in 20 seconds, but conservation of bandwidth prevents you from sending to 2 nodes in 10 seconds (assuming that the downloaders can saturate your upstream connection, which they most always can).
No, the file contents is also signed. Maybe part of the documentation is confusing when it comes to this point.... please point out where so that I can fix it.
--Jason