Timeline for Calculate the permanent as quickly as possible
Current License: CC BY-SA 3.0
40 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 24, 2016 at 0:21 | history | edited | Christian Sievers | CC BY-SA 3.0 |
update result
|
| Oct 31, 2016 at 1:43 | history | edited | Christian Sievers | CC BY-SA 3.0 |
simple code is faster :-)
|
| Oct 29, 2016 at 13:03 | comment | added | Christian Sievers | @Lembik For the new version, please note the added compiler options | |
| Oct 29, 2016 at 12:59 | history | edited | Christian Sievers | CC BY-SA 3.0 |
rewrite prod, extra compiler options
|
| Oct 27, 2016 at 16:05 | comment | added | Christian Sievers |
@Angs Yes, completely experimental and totally not understood by me. The number is higher than expected, and statistics (with run time option -s) still sometimes show GC'ed sparks (why does that happen at all?), but lowering the number such that most sparks are converted slightly increases execution time.
|
|
| Oct 27, 2016 at 15:37 | comment | added | Angs |
By the way, is the 11 experimental or how did you end up with it?
|
|
| Oct 27, 2016 at 14:20 | history | edited | Christian Sievers | CC BY-SA 3.0 |
update result
|
| Oct 27, 2016 at 14:10 | comment | added | Angs |
@ChristianSievers I thought I had but I had rolled my own main and forgot to change p to pt.
|
|
| Oct 27, 2016 at 10:44 | comment | added | Christian Sievers |
@Lembik Yes, all the things @Angs said, and you can undo the optimization for the odd case, which costs almost nothing, but is completely useless after undoing the also useless product optimization: in main replace pt with p, and remove the definition of pt. (And ofprod. And the last two import lines.) @Angs, do you have that optimization? With it I'm back to smoothly increasing running times.
|
|
| Oct 27, 2016 at 8:59 | comment | added | Angs |
@lembik that's weird. I was wondering because on my system, n+1 is always faster than n when n is odd. You can also change m * prod p to m * V.product p because with floating point inputs the optimization won't work.
|
|
| Oct 27, 2016 at 8:38 | comment | added | user9206 | @Angs Thank you.There is a great deal of non-determinism in the run times so I ran it a few more times and eventually got to 57 seconds for n - 30 :) | |
| Oct 27, 2016 at 8:00 | comment | added | Angs |
@lembik I think I can answer that for you: just replace all Int8 and Integer with Double, remove the fromIntegral and change _`div`_ to /. Was n=30 close? :)
|
|
| Oct 27, 2016 at 7:02 | comment | added | user9206 | Faster again! Out of interest, how hard would it be for your code to support floating point inputs? | |
| Oct 27, 2016 at 2:57 | history | edited | Christian Sievers | CC BY-SA 3.0 |
8 bit are enough and seem slightly faster
|
| Oct 27, 2016 at 0:10 | comment | added | Christian Sievers | @Angs Thanks for your observation that there are no zeros in the odd n case. It's obvious in hindsight, but I may not have noticed it. (It also explains that my results with 29x29, 30x30 and 31x31 matrices were nothing special.) Now that you made me think about it, I found a way to force zeros into the odd case. | |
| Oct 27, 2016 at 0:00 | history | edited | Christian Sievers | CC BY-SA 3.0 |
transform to put zeros into the odd case
|
| Oct 26, 2016 at 18:46 | comment | added | user9206 | Much faster indeed! | |
| Oct 26, 2016 at 15:26 | comment | added | Christian Sievers | @Angs But that's only true for this special kind of input. And the overhead isn't that bad. | |
| Oct 26, 2016 at 14:53 | comment | added | Angs |
@christian-sievers Yeah, I was about to say something about that product but forgot. It seems only even lengths have zeros in p, so for odd length we should use the regular product instead of the short circuiting to get the best of both worlds.
|
|
| Oct 26, 2016 at 14:31 | comment | added | Christian Sievers |
@Angs Great! I changed that into a form that doesn't need Transversable (I see your not changing product eatlier was no mistake...) for ghc from e.g. Debian stable. It's using the form of the input, but that seems fine: we're not relying on it, only optimizing for it. Makes timing much more exciting: my random 30x30 matrix is slightly faster than 29x29, but then 31x31 take 4x time. - That INLINE doesn't seem to work for me. AFAIK it's ignored for recursive functions.
|
|
| Oct 26, 2016 at 13:38 | history | edited | Christian Sievers | CC BY-SA 3.0 |
short circuit product
|
| Oct 26, 2016 at 11:35 | comment | added | Angs |
@christian-sievers glab I could be of help. Here's another fun luck-based optimization I found: x p _ m _ = m * (sum $ V.foldM' (\a b -> if b==0 then Nothing else Just $ a*fromIntegral b) 1 p) - product as a monadic fold where 0 is a special case. Seems to be beneficial more often than not.
|
|
| Oct 26, 2016 at 1:50 | history | edited | Christian Sievers | CC BY-SA 3.0 |
cleanup
|
| Oct 26, 2016 at 0:14 | comment | added | Christian Sievers |
@Angs Thanks a lot! I didn't really feel like looking into better suited datatypes. It's amazing how little things have to change (also had to use V.product). That only gave me ~10%. Changed the code so that the vectors only contain Ints. That's okay because they are only added, the big numbers come from multiplication. Then it was ~20%. I had tried the same change with the old code, but at that time it slowed it down. I tried again because it allows to use unboxed vectors, which helped a lot!
|
|
| Oct 26, 2016 at 0:00 | history | edited | Christian Sievers | CC BY-SA 3.0 |
use Vector
|
| Oct 25, 2016 at 15:19 | comment | added | Angs |
I was able to get a speed improvement of 20-25% by plugging in Data.Vector. The changes excluding changed function types: import qualified Data.Vector as V, x (V.zipWith(-) p v) vs (-m) c' ), p (v:vs) = x (foldl (V.zipWith (+)) v vs) (map (V.map (2*)) vs) 1 11, main = getContents >>= print . p . map V.fromList . read
|
|
| Oct 23, 2016 at 20:14 | history | edited | Christian Sievers | CC BY-SA 3.0 |
official result
|
| Oct 23, 2016 at 19:30 | comment | added | user9206 | This is my testing code bpaste.net/show/e74c87dfd19d in case you want to try it. | |
| Oct 23, 2016 at 19:28 | comment | added | Christian Sievers | Oh, I hoped for more with 8 cores... | |
| Oct 23, 2016 at 19:26 | comment | added | user9206 | My mistake! Makes it to 26 now. | |
| Oct 23, 2016 at 19:23 | history | edited | Christian Sievers | CC BY-SA 3.0 |
remove double type declaration
|
| Oct 23, 2016 at 19:20 | comment | added | Christian Sievers | Oops, that's the result of partially changing the code. Did you use the specified runtime parameters? | |
| Oct 23, 2016 at 19:07 | comment | added | user9206 | Thank you. Some comments. line 3 is repeated in the source. Also it doesn't seem to actually run in parallel. At least "top" doesn't show more than 1 core working. | |
| Oct 23, 2016 at 17:50 | history | edited | Christian Sievers | CC BY-SA 3.0 |
no inner rpar needed
|
| Oct 23, 2016 at 16:01 | history | edited | Christian Sievers | CC BY-SA 3.0 |
can't wait for the results
|
| Oct 23, 2016 at 15:30 | history | edited | Christian Sievers | CC BY-SA 3.0 |
better style (I hope), and correct name
|
| Oct 23, 2016 at 15:23 | history | edited | Christian Sievers | CC BY-SA 3.0 |
better style (I hope)
|
| Oct 23, 2016 at 11:12 | history | edited | Christian Sievers | CC BY-SA 3.0 |
improved version
|
| Oct 23, 2016 at 1:48 | history | edited | Christian Sievers | CC BY-SA 3.0 |
this seems to be better
|
| Oct 23, 2016 at 1:33 | history | answered | Christian Sievers | CC BY-SA 3.0 |