Update array.fs #854
Update array.fs #854
Conversation
*copied from fsharp/fsharp#533 There may be a missing length check on exists, as without hte length check the cost of a comparison and a `call` is incurred. Adding the simple len > 0 check before the loop appears (in the basic cases I have tested) to near triple performance. ``` let f arr = Array.exists (fun e -> e = true) arr for i in 0..60000000 do f ([||]:bool []) ;; // 1.8 seconds let f2 arr = if Array.length arr > 0 then Array.exists (fun e -> e = true) arr else false for i in 0..60000000 do f2 ([||]:bool []) ;; // 0.430 seconds ``` Note: this is something I have found an isolated instance of, it may be appropriate to ensure that such checks (if they are required, I can only speak for my use case) are consistant accross other modules, such as Seq\List.
|
Hi @xenocons, I'm your friendly neighborhood Microsoft Pull Request Bot (You can call me MSBOT). Thanks for your contribution! TTYL, MSBOT; |
|
👍 |
|
Are you sure your changes give the same perf advantage? Looks like the first call to the inner loop function has the same check. So you are optimizing one function call, right? |
|
@forki according to my quick test on my machine with the inner implementation: about 100ms for 60 billion calls |
|
So it's indeed faster, but only a little bit. I wonder if a loop would be
|
|
@forki I'm not good at loops, it's so imperative :) |
|
yeah, but computers are really good in such things. |
|
@mexx your same code on my PC, win10,16GB RAM,i7-4600U @ 2.10GHz, 64bit, 32bit FSI with --optimize: |
|
Mhm. What about 1 element arrays? IIRC we have lots of functions that do: On Jan 8, 2016 00:46, "David Klein" [email protected] wrote:
|
|
FWIW, debug builds of originals, exists orig takes 20 instructions if empty array, exists2 takes 6 IL instructions if empty, this becomes clearer when you look at the assembler, exists2 exits the function reasonably efficiently. I guess the question is, how often is the input to exists an empty array? In my case it happens a lot, but it turns out to be more efficient to do the Length = 0 check at the site of the my function that calls exists, rather than allow it to go into FSharp.Core first (as each function call incurs a cost), but from my personal expectations, I would assume something like exists to return immediately on empty, but once again this is my own personal tilt: update:fixed paragraphing and spelling |
|
@xenocons Do we have any measurements of memory usage, allocations and wall clock improvements associated with this change? Thanks Kevin |
|
@KevinRansom Is there a suggested methodology for producing such information (apart from counting the number of x86 instructions and the cycle count)? |
|
@KevinRansom - The perf results are here: #854 (comment). I think those results are sufficient. I'm happy with this change, it is reasonable to check once for emptiness early to avoid the call. So we can pull this. |
6 participants
copied from fsharp/fsharp#533
There may be a missing length check on exists, as without hte length check the cost of a comparison and a
callis incurred.Adding the simple len > 0 check before the loop appears (in the basic cases I have tested) to near triple performance.
Note: this is something I have found an isolated instance of, it may be appropriate to ensure that such checks (if they are required, I can only speak for my use case) are consistant accross other modules, such as Seq\List.