3 ms·

> 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 significa

> 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.

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.