Logs: liberachat/#haskell
| 2021-06-21 08:48:34 | <siraben> | merijn: cache reasons? |
| 2021-06-21 08:48:37 | <kuribas> | merijn: less copying |
| 2021-06-21 08:48:47 | <merijn> | kuribas: That only applies if you mutate |
| 2021-06-21 08:48:59 | <kuribas> | merijn: also if you need to store them |
| 2021-06-21 08:49:02 | <kuribas> | and retrieve |
| 2021-06-21 08:49:02 | <siraben> | IIRC, the kind of linked lists one learns in undergrad CS is woefully slow compared to unrolled link lists |
| 2021-06-21 08:49:16 | <siraben> | s/link/linked/ |
| 2021-06-21 08:49:25 | <merijn> | siraben: Right, but Haskell lists are the dreadful type ;) |
| 2021-06-21 08:49:38 | <siraben> | yeah |
| 2021-06-21 08:49:40 | <kuribas> | siraben: for code contests it's rarely the language or implementation that matters, usually just the algorithmic complexity. |
| 2021-06-21 08:49:41 | <siraben> | but lists aren't always so bad, IME |
| 2021-06-21 08:50:01 | <siraben> | if you do a single pass and use folds correctly, they can be quite performant |
| 2021-06-21 08:50:11 | <siraben> | kuribas: yeah |
| 2021-06-21 08:50:12 | <EvanR> | because they get compiled away entirely? xD |
| 2021-06-21 08:50:18 | <int-e> | Haskell's lists are so convenient though... I usually start out with lists and then replace them by some kind of array (Data.Vector is an array in that view) if performance becomes an issue. |
| 2021-06-21 08:50:19 | <siraben> | it is annoying to do these problems when I wish I could "just" mutate a structure |
| 2021-06-21 08:50:24 | <EvanR> | no list is definitely fast |
| 2021-06-21 08:50:28 | <siraben> | that I know I'm handling in a linear way, so in-place should be fine |
| 2021-06-21 08:50:29 | <maerwald[m]> | If you're lucky that fusion triggers you mean |
| 2021-06-21 08:50:37 | <siraben> | maerwald: yeah |
| 2021-06-21 08:50:44 | <siraben> | IntSet and IntMap are really fast, IME |
| 2021-06-21 08:50:50 | → | dka_ joins (~code-is-a@ns3059207.ip-193-70-33.eu) |
| 2021-06-21 08:50:54 | <kuribas> | siraben: leverage lazyness? |
| 2021-06-21 08:51:02 | <siraben> | probably I've use IntMap much more than laziness |
| 2021-06-21 08:51:07 | <kuribas> | siraben: I find most of these problems have nice elegant lazy solution |
| 2021-06-21 08:51:12 | <siraben> | s/use/used/ s/laziness/arrays/ |
| 2021-06-21 08:51:15 | <int-e> | And of course there's all those cases where you use lists intermittently and rely on fusion for them to mostly disappear. |
| 2021-06-21 08:51:34 | <siraben> | kuribas: lol https://github.com/siraben/haoc-2020/blob/master/day3.hs |
| 2021-06-21 08:51:38 | <merijn> | siraben: Well, it depends on how you define "bad" :) |
| 2021-06-21 08:51:47 | <siraben> | `part2 i = let (a, b, c, d, e, _) = foldl' f (0, 0, 0, 0, 0, 1) (tail i) in a * b * c * d * e` "oops" |
| 2021-06-21 08:51:52 | <merijn> | siraben: Like I said, not everything actually needs "high performance" |
| 2021-06-21 08:52:11 | <merijn> | And there's no point investing effort into optimising something that doesn't need optimisation |
| 2021-06-21 08:52:21 | <siraben> | merijn: yeah of course, I'm also interested in how to get the fastest possible especially for toy problems |
| 2021-06-21 08:52:29 | <siraben> | in practice it may not matter when I/O, network is far slower |
| 2021-06-21 08:52:31 | × | dka_ quits (~code-is-a@ns3059207.ip-193-70-33.eu) (Remote host closed the connection) |
| 2021-06-21 08:52:48 | <siraben> | reducing branches actually does wonders |
| 2021-06-21 08:52:55 | → | dka joins (~code-is-a@ns3059207.ip-193-70-33.eu) |
| 2021-06-21 08:52:59 | <merijn> | siraben: So of course lists are convenient when the performance of something isn't immediately crucial. Especially since GHC has quite some effort on optimising list transformations |
| 2021-06-21 08:53:40 | × | hegstal quits (~hegstal@2a02:c7f:7604:8a00:2a76:42b9:78db:d162) (Remote host closed the connection) |
| 2021-06-21 08:53:54 | <EvanR> | any time casual performance concerns come up, I remind everyone the internet is based on PHP and ruby on rails |
| 2021-06-21 08:54:01 | → | jespada joins (~jespada@90.254.247.46) |
| 2021-06-21 08:54:07 | <kuribas> | and Python! |
| 2021-06-21 08:54:08 | <siraben> | merijn: ok, here's a good example, how can I avoid V.cons here? |
| 2021-06-21 08:54:08 | <siraben> | https://github.com/siraben/morans/blob/bb1e65b26d83188ea81b6509e7d340d8af94ee48/morans.hs#L55 |
| 2021-06-21 08:54:25 | <siraben> | it needs to be performant since this is a neural net in haskell |
| 2021-06-21 08:54:37 | <siraben> | I got the running time down from 45 s to around 22s |
| 2021-06-21 08:54:44 | <siraben> | just by translating the code to vectors |
| 2021-06-21 08:54:49 | <int-e> | siraben: kiss: https://paste.debian.net/1201880/ |
| 2021-06-21 08:54:50 | <siraben> | but V.cons is linear in the size of the vector >.< |
| 2021-06-21 08:55:11 | <merijn> | siraben: You're just constructing a new result vector from some input, right? |
| 2021-06-21 08:55:12 | <Taneb> | siraben: can you turn it into a scan rather than a fold? |
| 2021-06-21 08:55:35 | × | econo quits (uid147250@user/econo) (Quit: Connection closed for inactivity) |
| 2021-06-21 08:55:39 | <EvanR> | instead of consing, you could use an endo builder |
| 2021-06-21 08:55:47 | <Taneb> | Ending with a vector of tuples which is easy to make into a tuple of vectors |
| 2021-06-21 08:55:49 | <siraben> | hm, it would be awesome if hlint had support for laws that require some precondition to be true, such as the foldl/scanl law |
| 2021-06-21 08:56:00 | <kuribas> | merijn: why would a chunked list be slower than one bug chunk (for large enough chunks). |
| 2021-06-21 08:56:01 | <merijn> | siraben: There are in-place construction functions for vector |
| 2021-06-21 08:56:14 | <EvanR> | instead of copying into new vectors each time, you build a thing you can iterate through later |
| 2021-06-21 08:56:48 | → | Ariakenom joins (~Ariakenom@2001:9b1:efb:fc00:315a:5813:efa5:bde0) |
| 2021-06-21 08:56:49 | <merijn> | siraben: I'd say you want something like generate instead: https://hackage.haskell.org/package/vector-0.12.3.0/docs/Data-Vector-Fusion-Stream-Monadic.html#v:generate |
| 2021-06-21 08:57:32 | <siraben> | int-e: yes, that's similar to my initial solution, I managed to get down from 39 μs to 26 μs by using bytestring and some strictness |
| 2021-06-21 08:57:46 | × | jneira quits (~jneira@212.8.115.226) (Quit: Client closed) |
| 2021-06-21 08:58:06 | → | jneira joins (~jneira@212.8.115.226) |
| 2021-06-21 08:58:24 | <merijn> | siraben: So instead of folding, running basically an indexed loop on the original vector, something like: https://github.com/merijn/Belewitte/blob/master/benchmark-analysis/src/StepAggregate.hs#L112-L116 |
| 2021-06-21 08:58:42 | <siraben> | ah, interesting, I could try that |
| 2021-06-21 08:58:46 | <siraben> | ooh, VS.unsafeIndex |
| 2021-06-21 08:59:03 | <merijn> | siraben: unsafeIndex skips bounds checking |
| 2021-06-21 08:59:15 | <merijn> | So great way to segfault your code if you don't know what you're doing ;) |
| 2021-06-21 08:59:30 | <siraben> | yeah, how much difference does it make? |
| 2021-06-21 08:59:39 | <merijn> | Very little |
| 2021-06-21 08:59:40 | <EvanR> | all you need is a proof you're in bounds |
| 2021-06-21 08:59:49 | <siraben> | this would be the type of stuff that refinement types (or full blown dep types) could help with |
| 2021-06-21 08:59:54 | <merijn> | but I'm using this in a tight loop where I do millions (maybe billions) of lookups :p |
| 2021-06-21 08:59:55 | <siraben> | EvanR: right |
| 2021-06-21 09:00:12 | <merijn> | So a billion times very little helps ;) |
| 2021-06-21 09:00:14 | <EvanR> | a real proof can be difficult to actually get and maintain |
| 2021-06-21 09:00:22 | <siraben> | I think the GOL type problems in AOC were more performance sensitive as well |
| 2021-06-21 09:00:29 | <int-e> | siraben: I tend not to optimize anything that runs in under a second when using runghc :) |
| 2021-06-21 09:00:44 | <merijn> | siraben: Anyway, the key point here is that generate basically allocates an empty vector and fills in every element with "Int -> a" (where the Int is the index) |
| 2021-06-21 09:01:06 | <siraben> | int-e: fair enough, as kuribas said, algorithmic efficiency can matter more even in CP problems |
| 2021-06-21 09:01:08 | <merijn> | siraben: So you can construct your result array "in place" if you can reformulate your fold into a function from index to a value |
| 2021-06-21 09:01:10 | <siraben> | merijn: yeah |
| 2021-06-21 09:01:21 | <merijn> | That will save all the cons copying |
| 2021-06-21 09:01:26 | <siraben> | the recursion pattern is a bit weird here |
| 2021-06-21 09:01:32 | <siraben> | in my function `revaz` |
| 2021-06-21 09:01:53 | <siraben> | because it calls the function zLayer defined as `zLayer as (bs, wvs) = V.zipWith (+) bs $ V.sum . V.zipWith (*) as <$> wvs` |
| 2021-06-21 09:02:01 | <siraben> | so in that sense, it's already quadratic |
| 2021-06-21 09:02:58 | → | mc47 joins (~mc47@xmonad/TheMC47) |
| 2021-06-21 09:03:14 | × | mc47 quits (~mc47@xmonad/TheMC47) (Remote host closed the connection) |
| 2021-06-21 09:03:38 | → | mc47 joins (~mc47@xmonad/TheMC47) |
| 2021-06-21 09:05:05 | → | MQ-17J joins (~MQ-17J@d14-69-206-129.try.wideopenwest.com) |
| 2021-06-21 09:06:53 | → | ocramz joins (~user@c80-216-51-213.bredband.tele2.se) |
| 2021-06-21 09:07:01 | <ocramz> | hullo! |
| 2021-06-21 09:07:31 | × | MQ-17J quits (~MQ-17J@d14-69-206-129.try.wideopenwest.com) (Read error: Connection reset by peer) |
| 2021-06-21 09:07:47 | → | MQ-17J joins (~MQ-17J@d14-69-206-129.try.wideopenwest.com) |
| 2021-06-21 09:08:56 | → | yoctocell joins (~user@h87-96-130-155.cust.a3fiber.se) |
| 2021-06-21 09:08:59 | <ocramz> | ghc-lib versus ghc-as-a-library : can I write a GHC plugin by importing only ghc-lib ? or, yes it does typecheck and the interface is the same as ghc library, but would it work when used by code that compiles against the ghc library ? |
| 2021-06-21 09:09:45 | × | yoctocell quits (~user@h87-96-130-155.cust.a3fiber.se) (Remote host closed the connection) |
| 2021-06-21 09:09:56 | × | azeem quits (~azeem@dynamic-adsl-94-34-49-60.clienti.tiscali.it) (Ping timeout: 258 seconds) |
| 2021-06-21 09:09:59 | × | chomwitt quits (~Pitsikoko@2a02:587:dc0b:ff00:c813:70d9:31b2:b1b9) (Ping timeout: 244 seconds) |
All times are in UTC.