Logs: freenode/#haskell
| 2021-03-04 23:16:41 | swarmcollective | wonders why sorting hasn't been moved to hardware level by now... |
| 2021-03-04 23:16:41 | <Axman6> | if if I hand you something of type Either (Word8, Char) (Maybe Bool), you have a finite set of buckets to pass those values into, and you know where they're going to end up a priori |
| 2021-03-04 23:17:08 | <infinisil> | Ah that makes sense |
| 2021-03-04 23:17:32 | <infinisil> | So as soon as you have infinite different values it won't work |
| 2021-03-04 23:18:00 | <infinisil> | (In O(n) with this approach) |
| 2021-03-04 23:18:06 | <Axman6> | The really cool thing to me about the discrimination package is the grouping, which allows you to take [a] and get back [[a]], where each [a] is productive - as soon as an element of the input is places into a group, you can process it |
| 2021-03-04 23:18:49 | <Axman6> | infinisil: yeah, and lots of useful types make this hard, like esoterric types such as String |
| 2021-03-04 23:18:50 | <infinisil> | Oh neat |
| 2021-03-04 23:18:54 | × | son0p quits (~son0p@181.136.122.143) (Quit: leaving) |
| 2021-03-04 23:18:56 | <dolio> | Radix sort doesn't have a bucket for every possible value. |
| 2021-03-04 23:19:12 | <dolio> | It has a bucket for every possible value of a chunk. |
| 2021-03-04 23:19:34 | <ByteEater> | I guess my question has the same answer as whether drop (length l) $ l ++ [x] can be evaluated (to [x]) in sublinear time – can drop instantly skip (thanks to some optimization) prefixes of known lengths |
| 2021-03-04 23:19:48 | <Axman6> | infinisil: probably a good idea to not look at the implementation of how grouping works, it's crazy low level, laziness reimplemented stuff. edwardk is a demon |
| 2021-03-04 23:19:55 | × | ollierees quits (~ollierees@2a02:c7f:a8a8:fb00:7bfd:a909:fc9a:92c6) (Quit: WeeChat 2.9) |
| 2021-03-04 23:20:04 | <infinisil> | It's.. |
| 2021-03-04 23:20:05 | <infinisil> | Too late! |
| 2021-03-04 23:20:45 | <monochrom> | Hardware people are too busy adding https://developer.arm.com/documentation/dui0801/g/A64-Floating-point-Instructions/FJCVTZS to add sorting. :) |
| 2021-03-04 23:20:47 | <Axman6> | Good luck understanding it! I did once |
| 2021-03-04 23:21:09 | <dolio> | I suppose it's possible that with infinite values, you could arrange for an array of size n to require log n passes to successfully partition, though. |
| 2021-03-04 23:21:31 | <infinisil> | I think that's what discrimination actually does with at least Integer |
| 2021-03-04 23:21:46 | <infinisil> | https://hackage.haskell.org/package/discrimination-0.4.1/docs/src/Data.Discrimination.Internal.html#integerCases |
| 2021-03-04 23:22:02 | <infinisil> | Splits it into (Int, [Word]) |
| 2021-03-04 23:22:14 | <infinisil> | Then probably groups by that |
| 2021-03-04 23:22:16 | <Axman6> | IIRC the Integer/Natural instance is less than optimal |
| 2021-03-04 23:23:35 | <monochrom> | "drop n xs", if xs is longer than n, takes n time. This can count as sublinear or exponential, depending on your perspective. |
| 2021-03-04 23:23:42 | × | Yumasi quits (~guillaume@2a01:e0a:5cb:4430:8c46:2884:8ca1:7346) (Ping timeout: 258 seconds) |
| 2021-03-04 23:23:43 | <dolio> | Anyhow, vector-algorithms also has a sort of radix sort that can sort strings. |
| 2021-03-04 23:24:07 | <Axman6> | monochrom: or this crap: https://en.wikipedia.org/wiki/X86_instruction_listings#SSE4.2 |
| 2021-03-04 23:24:32 | <monochrom> | hehe |
| 2021-03-04 23:24:36 | × | cgadski quits (~textual@a95-95-106-208.cpe.netcabo.pt) (Quit: My MacBook has gone to sleep. ZZZzzz…) |
| 2021-03-04 23:24:47 | <Axman6> | https://software.intel.com/content/www/us/en/develop/articles/schema-validation-with-intel-streaming-simd-extensions-4-intel-sse4.html just batshit crazy |
| 2021-03-04 23:25:21 | <monochrom> | Well, if strncmp() gets hardwarized, I think sort() has hope tomorrow. |
| 2021-03-04 23:26:10 | × | ystael quits (~ystael@209.6.50.55) (Read error: Connection reset by peer) |
| 2021-03-04 23:26:56 | <dolio> | Good thing they added all that fancy stuff so they could get smoked by a RISC chip. :þ |
| 2021-03-04 23:27:23 | → | ystael joins (~ystael@209.6.50.55) |
| 2021-03-04 23:27:40 | <Axman6> | ByteEater: you could add an optimisation that does that, or you also just not write that code in the first place, the compiler can only make up for your crappy code so far :) Also, what if l is infinite? |
| 2021-03-04 23:28:30 | <Axman6> | dolio: yeah the next few years of Apple hardware (and likely other ARM hardware) are going to be very interesting. |
| 2021-03-04 23:28:49 | <koz_> | I wonder how long till we get a WTFBBQ instruction. |
| 2021-03-04 23:28:56 | <Axman6> | Hey, looks like Intel invented Spongebob speak! "atomic CoMPare and eXCHanGe" |
| 2021-03-04 23:29:14 | <monochrom> | What should the WTFBBQ instruction do? |
| 2021-03-04 23:29:20 | <koz_> | Axman6: Hats off for PQLMULQDQ |
| 2021-03-04 23:29:21 | × | pfurla quits (~pfurla@pool-108-6-43-243.nycmny.fios.verizon.net) (Quit: gone to sleep. ZZZzzz…) |
| 2021-03-04 23:29:21 | × | Franciman quits (~francesco@host-82-49-79-189.retail.telecomitalia.it) (Quit: Leaving) |
| 2021-03-04 23:29:27 | → | wroathe joins (~wroathe@c-68-54-25-135.hsd1.mn.comcast.net) |
| 2021-03-04 23:29:29 | <dolio> | I guess to be fair, part of the advantage is other on-board dedicated chips (just not direct CPU instructions maybe). |
| 2021-03-04 23:29:38 | <koz_> | monochrom: Judging by how the others are named? Whatever you feel like. |
| 2021-03-04 23:29:43 | <koz_> | You can always back-justify it. |
| 2021-03-04 23:30:08 | <Axman6> | With This Function Byte Broadcast Quadword |
| 2021-03-04 23:30:17 | Axman6 | sends in an application to Intel |
| 2021-03-04 23:30:19 | <ByteEater> | just checked experimentally (though probably not with all possible optimization flags) and indeed even drop (length xs) xs seems to take linear time to evaluate to [] |
| 2021-03-04 23:30:31 | <Axman6> | of course it does |
| 2021-03-04 23:30:37 | <koz_> | That is wholly unsurprising. |
| 2021-03-04 23:30:45 | <ByteEater> | when xs is a small, unevaluated thunk initially |
| 2021-03-04 23:30:58 | → | Tario joins (~Tario@201.192.165.173) |
| 2021-03-04 23:31:08 | <Axman6> | if I pass in [1..], I expect that function to take forever to never return [] |
| 2021-03-04 23:31:12 | <monochrom> | "with this function" sounds like a higher-order function. |
| 2021-03-04 23:31:28 | <Axman6> | You;'re attributing much more magic to the compiler than it deserves |
| 2021-03-04 23:31:30 | <monochrom> | "WTFBBQ the first higher-order-function instruction" |
| 2021-03-04 23:31:31 | <ByteEater> | yes, with infinite lists there's no length, or median |
| 2021-03-04 23:31:41 | <Axman6> | monochrom: yeah it sure is |
| 2021-03-04 23:32:11 | <shachaf> | Axman6: Let me know when you can sort a list of reals in linear time. |
| 2021-03-04 23:32:16 | <shachaf> | Not that I'm even sure what that means exactly. |
| 2021-03-04 23:32:30 | <ByteEater> | I hoped there'd be some rewrite rule allowing drop to be optimized and reach only for the part that needs evaluating |
| 2021-03-04 23:32:42 | <dolio> | shachaf: Just use the axiom of choice. |
| 2021-03-04 23:32:47 | <monochrom> | hahaha |
| 2021-03-04 23:33:10 | <Axman6> | shachaf: that sounds... really hard =) |
| 2021-03-04 23:33:29 | <shachaf> | Well, you can write a program to sort computable reals. |
| 2021-03-04 23:33:34 | <ByteEater> | probably it can be written for such simple cases, but from its absence I fathom it wasn't found easily generalizable to non-trivial cases and thus forgone |
| 2021-03-04 23:33:55 | <shachaf> | I just don't know what it means to say how long it takes. I guess you can measure the size of a sorting network. |
| 2021-03-04 23:34:00 | <int-e> | shachaf: would you use a sorting network? |
| 2021-03-04 23:34:10 | <monochrom> | You can take almost forever sorting even two computable reals, so nevermind a list of them. |
| 2021-03-04 23:34:34 | <int-e> | monochrom: but you /can/ compute the minimum and the maximum of both |
| 2021-03-04 23:34:34 | × | ukari quits (~ukari@unaffiliated/ukari) (Remote host closed the connection) |
| 2021-03-04 23:34:35 | <shachaf> | Well, \x y -> (min x y, max x y) doesn't take almost forever. |
| 2021-03-04 23:34:40 | <int-e> | monochrom: which is sorting them |
| 2021-03-04 23:34:45 | × | fissureman quits (~quassel@c-73-201-159-163.hsd1.dc.comcast.net) (Ping timeout: 246 seconds) |
| 2021-03-04 23:34:48 | <ByteEater> | on the other hand, if the type included length (that'd require dependent types), the optimization in general would seem quite straightforward |
| 2021-03-04 23:34:54 | <monochrom> | Oh, then I have to bump up to 3 computable reals. |
| 2021-03-04 23:35:03 | <int-e> | monochrom: now you use a sorting network |
| 2021-03-04 23:35:18 | <int-e> | to reduce to the case of sorting two values |
| 2021-03-04 23:35:37 | <dolio> | How long does it take to produce a sorting network for n values? |
| 2021-03-04 23:35:39 | <monochrom> | Isn't it fascinating? Most "k-Foo" problems have a great complexity divide when jumping from k=2 to k=3. |
| 2021-03-04 23:35:53 | → | ukari joins (~ukari@unaffiliated/ukari) |
| 2021-03-04 23:36:10 | <int-e> | dolio: https://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort is very easy to compute |
| 2021-03-04 23:36:48 | × | kiweun quits (~kiweun@2607:fea8:2a62:9600:8160:4d43:4a85:f4b8) (Remote host closed the connection) |
| 2021-03-04 23:36:56 | <koz_> | ByteEater: This is very hard to do in general. |
| 2021-03-04 23:37:03 | <koz_> | It _might_ work if your Int argument is a constant. |
| 2021-03-04 23:37:14 | <koz_> | But it can be computed more-or-less however you feel like. |
| 2021-03-04 23:38:22 | <monochrom> | Dependent typing will not turn GHC into Lean+Mathematica. |
| 2021-03-04 23:38:51 | <Axman6> | not with that attitude it won't |
| 2021-03-04 23:39:12 | <dolio> | O(n (log n)^2) space usage suggests it's not linear to figure it out dynamically, I guess? |
| 2021-03-04 23:39:35 | × | conal quits (~conal@64.71.133.70) (Quit: Computer has gone to sleep.) |
| 2021-03-04 23:39:40 | <shachaf> | Well, a sorting network is a comparison sort, so it'll have more than linearly many comparisons. |
| 2021-03-04 23:40:03 | <shachaf> | (Or min-maxes in this case.) |
| 2021-03-04 23:40:07 | <dolio> | Right. |
| 2021-03-04 23:40:15 | <monochrom> | That is not an attitude. That is an observation of the people who work on GHC, what they're interested in and what they aren't. |
| 2021-03-04 23:40:59 | <dolio> | Your real numbers probably aren't going to be performing great afterward, either. |
| 2021-03-04 23:41:31 | <Axman6> | Would we be better off with hypothetical numbers? |
| 2021-03-04 23:41:42 | <ByteEater> | OK, now I understand it better, thanks |
| 2021-03-04 23:41:45 | <monochrom> | And even if I'm right for only the next 10 years and then I'll be wrong, that's still long enough time for most practical purposes. |
All times are in UTC.