4 ms·

Which section are you referring to? 2.1, 2.2 maybe? Sorry of for the simple question, but I think I'm missing something. Wouldn't avoiding a destructive upda

by jxm262 12y ago

Which section are you referring to? 2.1, 2.2 maybe? Sorry of for the simple question, but I think I'm missing something. Wouldn't avoiding a destructive update give better performance? And the trade-off would be higher maintainability? With a mutable structure, you're 'destroying' just reusing the same locations in memory and just replacing, versus say an immutable structure returning a completely new structure (new memory allocations). But to your main point, yes I won't take this as the canonical source of coding standards. I just like to read through stuff like this because it gives me alot of areas to explore and research. Like why do this vs that, what's the tradeoffs, etc.. <<edit>> Whoop's looks like i have my logic/terminology flipped! Saw this on SO which cleared things up a bit. http://stackoverflow.com/questions/6964233/what-is-a-destructive-update http://stackoverflow.com/questions/6964233/what-is-a-destruc... Also just noticed the + vs += in some of the mutable collections, which helps to explain.

rbehrends 12y ago
> Which section are you referring to? 2.1, 2.2 maybe? Much of section 2 and 4. Also, I'm not using Play, Akka, or any other web frameworks (since I don't do web stuff), so those don't apply to me and I don't have a basis for evaluating them. > Wouldn't avoiding a destructive update give better performance? No. In the absence of destructive updates, you either need to copy matrices or use a data structure that typically incurs a log(n) overhead with a fairly large constant.
- jxm262 12y ago
  Thanks, I think I get it now. Helps when I actually read the API's :)
- bad_user 12y ago
  > In the absence of destructive updates, you either need to copy matrices or use a data structure that typically incurs a log(n) overhead with a fairly large constant. That is not true - first of all, log(n) in our industry means log2(n). Scala's Vector for example is a log32(n), which given that the max size is Int.MaxValue, can be treated as constant access as far as algorithmic complexity is concerned. Persistent HashMaps are also implemented (instead of self-balancing binary trees), which again means less than log2(n). And Scala's Queue for example is O(1) for both enqueue() and dequeue() - it's just that every "n" operations it has to invert a list of pending items, which takes "O(n)" but given that it happens every "n" operations it is amortized. It's not algorithmic complexity that bites you, algorithmic complexity is totally fine. The real problem is more low level, with the indirections happening due to usage of pointers. Depending on memory usage patterns, persistent data-structures could stress the GC enough to increase the number of stop-the-world pauses. Also in a multi-threading context, when you keep the pounding on the same reference holding an immutable data-structure, you drive the contention to the root of that tree and that is less efficient than a specialized mutable data-structure that can distribute those locks in multiple buckets ... but still far better than synchronizing on a standard mutable data-structure. Actually, which is better in terms of performance depends on context. For example if you have shared reads, then an immutable data-structure is better because you do not need to synchronize those reads. Also - I did work on a web service that was hit with tens of thousands of requests per second and because of the architecture we've built (asynchronous single producers, multi consumers), usage of immutable data-structures wasn't an issue and it was much saner. AND most people working on most project never end up with such hard optimization issues. Therefore fear-mongering about something that in practice really is not an issue is not helpful, especially given the sanity that usage of immutable data-structures brings. See this other rule I added - https://github.com/alexandru/scala-best-practices/blob/master/sections/3-architecture.md#33-should-not-apply-optimizations-without-profiling https://github.com/alexandru/scala-best-practices/blob/maste...
  - rbehrends 12y ago
    > That is not true - first of all, log(n) in our industry means log2(n) Which, for a 1000x1000 matrix, means a factor of about 20, not to mention the significant constant overhead from not using a contiguous memory layout. > It's not algorithmic complexity that bites you, algorithmic complexity is totally fine. I didn't say anything about algorithmic complexity. Note that I was writing log(n), not O(log(n)) in particular and pointing at the constant factor, too. A computation that takes two days instead of half an hour does make a very real difference to me. > I did work on a web service that [...] That's why I was careful to point out how different application domains matter. Web services are not numerical computations are not computer algebra are not big data.
    - bad_user 12y ago
      > A computation that takes two days instead of half an hour does make a very real difference to me IMHO, such a big difference only arrises when big differences in algorithmic complexity is involved. Again I must mention that I'm of the opinion that if you know what you're doing, then it's fine, but you must be able to defend your choice, as an argument like "gosh, heard from the Internet that immutable data-structures are slower" is not acceptable given the extra sanity that it brings. Plus, depending on context (e.g. web services that are dealing with parallelism combined with I/O) immutable data-structures might actually improve throughput. Your use-case is entirely legitimate, therefore that rule on usage of immutable data-structures is a SHOULD (optional), rather than a MUST (required). If you wanna do it, then do it - after all, the ability to get down and dirty is one thing I like about Scala, too bad that it doesn't have a GC-less version :-)
      - rbehrends 12y ago
        > IMHO, such a big difference only arrises when big differences in algorithmic complexity is involved. No, this arises as the result of large constant factors, too. As I pointed out, log2(1e6) is approximately a factor of 20 alone and you pay additional constant overhead for having suboptimal memory layout and allocations. Remember, while functional programming languages love trees and linked lists, the hardware loves contiguous arrays. This is what the L1 and L2 cache and prefetching logic of your typical CPU are optimized for.

by jxm262 12y ago

rbehrends 12y ago

> Which section are you referring to? 2.1, 2.2 maybe? Much of section 2 and 4. Also, I'm not using Play, Akka, or any other web frameworks (since I don't do web stuff), so those don't apply to me and I don't have a basis for evaluating them. > Wouldn't avoiding a destructive update give better performance? No. In the absence of destructive updates, you either need to copy matrices or use a data structure that typically incurs a log(n) overhead with a fairly large constant.

jxm262 12y ago
Thanks, I think I get it now. Helps when I actually read the API's :)
bad_user 12y ago
> In the absence of destructive updates, you either need to copy matrices or use a data structure that typically incurs a log(n) overhead with a fairly large constant. That is not true - first of all, log(n) in our industry means log2(n). Scala's Vector for example is a log32(n), which given that the max size is Int.MaxValue, can be treated as constant access as far as algorithmic complexity is concerned. Persistent HashMaps are also implemented (instead of self-balancing binary trees), which again means less than log2(n). And Scala's Queue for example is O(1) for both enqueue() and dequeue() - it's just that every "n" operations it has to invert a list of pending items, which takes "O(n)" but given that it happens every "n" operations it is amortized. It's not algorithmic complexity that bites you, algorithmic complexity is totally fine. The real problem is more low level, with the indirections happening due to usage of pointers. Depending on memory usage patterns, persistent data-structures could stress the GC enough to increase the number of stop-the-world pauses. Also in a multi-threading context, when you keep the pounding on the same reference holding an immutable data-structure, you drive the contention to the root of that tree and that is less efficient than a specialized mutable data-structure that can distribute those locks in multiple buckets ... but still far better than synchronizing on a standard mutable data-structure. Actually, which is better in terms of performance depends on context. For example if you have shared reads, then an immutable data-structure is better because you do not need to synchronize those reads. Also - I did work on a web service that was hit with tens of thousands of requests per second and because of the architecture we've built (asynchronous single producers, multi consumers), usage of immutable data-structures wasn't an issue and it was much saner. AND most people working on most project never end up with such hard optimization issues. Therefore fear-mongering about something that in practice really is not an issue is not helpful, especially given the sanity that usage of immutable data-structures brings. See this other rule I added - https://github.com/alexandru/scala-best-practices/blob/master/sections/3-architecture.md#33-should-not-apply-optimizations-without-profiling https://github.com/alexandru/scala-best-practices/blob/maste...
- rbehrends 12y ago
  > That is not true - first of all, log(n) in our industry means log2(n) Which, for a 1000x1000 matrix, means a factor of about 20, not to mention the significant constant overhead from not using a contiguous memory layout. > It's not algorithmic complexity that bites you, algorithmic complexity is totally fine. I didn't say anything about algorithmic complexity. Note that I was writing log(n), not O(log(n)) in particular and pointing at the constant factor, too. A computation that takes two days instead of half an hour does make a very real difference to me. > I did work on a web service that [...] That's why I was careful to point out how different application domains matter. Web services are not numerical computations are not computer algebra are not big data.
  - bad_user 12y ago
    > A computation that takes two days instead of half an hour does make a very real difference to me IMHO, such a big difference only arrises when big differences in algorithmic complexity is involved. Again I must mention that I'm of the opinion that if you know what you're doing, then it's fine, but you must be able to defend your choice, as an argument like "gosh, heard from the Internet that immutable data-structures are slower" is not acceptable given the extra sanity that it brings. Plus, depending on context (e.g. web services that are dealing with parallelism combined with I/O) immutable data-structures might actually improve throughput. Your use-case is entirely legitimate, therefore that rule on usage of immutable data-structures is a SHOULD (optional), rather than a MUST (required). If you wanna do it, then do it - after all, the ability to get down and dirty is one thing I like about Scala, too bad that it doesn't have a GC-less version :-)
    - rbehrends 12y ago
      > IMHO, such a big difference only arrises when big differences in algorithmic complexity is involved. No, this arises as the result of large constant factors, too. As I pointed out, log2(1e6) is approximately a factor of 20 alone and you pay additional constant overhead for having suboptimal memory layout and allocations. Remember, while functional programming languages love trees and linked lists, the hardware loves contiguous arrays. This is what the L1 and L2 cache and prefetching logic of your typical CPU are optimized for.