Logs: liberachat/#haskell
| 2025-12-02 16:34:41 | <lucabtz> | yeah |
| 2025-12-02 16:34:51 | × | lucabtz quits (~lucabtz@user/lucabtz) (Remote host closed the connection) |
| 2025-12-02 16:35:03 | × | trickard quits (~trickard@cpe-85-98-47-163.wireline.com.au) (Read error: Connection reset by peer) |
| 2025-12-02 16:36:27 | <merijn> | c_wraith: I'm not convinced that buys you anything over just straight up Map |
| 2025-12-02 16:38:17 | → | trickard_ joins (~trickard@cpe-85-98-47-163.wireline.com.au) |
| 2025-12-02 16:40:53 | <c_wraith> | I mean, unordered-containers is generally faster than containers. |
| 2025-12-02 16:41:50 | <c_wraith> | (the higher branching factor of a HAMT over a binary tree is significant) |
| 2025-12-02 16:42:45 | <merijn> | c_wraith: I mean, that's entirely dependent on workload, key type, and access pattern |
| 2025-12-02 16:43:48 | <merijn> | Not to mention the question whether that's even the hot part of your code |
| 2025-12-02 16:49:01 | <merijn> | Which pretty much brings us back to the initial question of "what's your key type and what makes you expect it's worth it to include Hashable over Ord" |
| 2025-12-02 16:49:16 | ← | Anarchos parts (~Anarchos@91-161-254-16.subs.proxad.net) () |
| 2025-12-02 16:51:49 | <c_wraith> | I rarely use unordered containers, for reasons of wanting to minimize dependencies and that collection performance usually doesn't matter. But whenever I've benchmarked my own code, it usually is faster. I just don't think it's enough faster to be worthwhile. |
| 2025-12-02 16:51:52 | <haskellbridge> | <loonycyborg> Constant time is still faster than logarithmic :P |
| 2025-12-02 16:52:26 | <c_wraith> | both constant time for hash tables and logarithmic time for binary trees are lies, of course |
| 2025-12-02 16:52:40 | <haskellbridge> | <loonycyborg> I think both unordered and ordered containers should be part of base |
| 2025-12-02 16:52:56 | <haskellbridge> | <loonycyborg> so people wouldn't have issues like above |
| 2025-12-02 16:54:11 | → | chromoblob joins (~chromoblo@user/chromob1ot1c) |
| 2025-12-02 16:54:51 | <c_wraith> | like, unordered-containers uses a HAMT instead of an array, because mutation forces you into an unpleasant API. That's a very fast data structure, but it's sure not O(1) for anything |
| 2025-12-02 16:55:16 | <c_wraith> | But it doesn't really matter that it's not O(1), because hashing isn't O(1) anyway, and never has been |
| 2025-12-02 16:56:00 | <c_wraith> | If you want to hash n values into O(n) buckets, you need to look at O(log n) bits of each value |
| 2025-12-02 16:57:06 | <haskellbridge> | <loonycyborg> On the other hand it's just matter of putting it to .cabal file and many other packages already use them so they're pretty much guaranteed to be pulled in.. |
| 2025-12-02 16:57:45 | <merijn> | looncyborg: Counter point: Since base changes requires new GHC releases they're slow to become widely available |
| 2025-12-02 16:58:00 | <merijn> | Now that could theoretically be fixed by decoupling base from GHC |
| 2025-12-02 16:58:19 | <merijn> | but that idea has been floating around since 2007 and still hasn't happened, so I would rather not hold my breath |
| 2025-12-02 16:58:24 | <c_wraith> | but by way of fairness, a binary tree is only O(log n) for stuff if comparisons are O(1), which is equally impossible |
| 2025-12-02 16:58:40 | × | tromp quits (~textual@2001:1c00:3487:1b00:4073:6a24:b181:8b56) (Ping timeout: 245 seconds) |
| 2025-12-02 16:59:09 | <c_wraith> | I don't know why schools teach both of those data structures so poorly. |
| 2025-12-02 16:59:18 | <merijn> | c_wraith: I mean, for something like Int they are (given the completely broken big O model) |
| 2025-12-02 16:59:28 | <merijn> | Then again if you have int, just use a PATRICIA tree |
| 2025-12-02 16:59:45 | <c_wraith> | if you have Int, everything is O(1), because it's a fixed-size domain |
| 2025-12-02 16:59:50 | <merijn> | c_wraith: Jokes on you, most schools don't teach either at all |
| 2025-12-02 16:59:53 | <merijn> | :p |
| 2025-12-02 16:59:55 | <haskellbridge> | <loonycyborg> Does it even make sense to use O notation for comparisons? Like they explicitly involve only two items, not entire list |
| 2025-12-02 17:00:14 | <haskellbridge> | <loonycyborg> And O is about how it scales with list length |
| 2025-12-02 17:00:42 | <merijn> | loonycyborg: Don't get me started on my usual rant of big O barely making sense at all in the real world :p |
| 2025-12-02 17:01:37 | <haskellbridge> | <loonycyborg> It makes as much sense as any other approximation |
| 2025-12-02 17:02:24 | <haskellbridge> | <loonycyborg> Just need to remember that it only says how algorithm scales with number of items in container |
| 2025-12-02 17:02:38 | <haskellbridge> | <loonycyborg> even O(1) can be dog slow |
| 2025-12-02 17:02:41 | <merijn> | loonycyborg: My complaint is that it doesn't even do that :p |
| 2025-12-02 17:02:47 | × | trickard_ quits (~trickard@cpe-85-98-47-163.wireline.com.au) (Ping timeout: 250 seconds) |
| 2025-12-02 17:02:50 | <merijn> | Or rather, it can be arbitrarily far off |
| 2025-12-02 17:02:57 | <c_wraith> | loonycyborg: to some extent. the number of distinct keys puts a lower bound on the comparison time. If you have 2^64 keys in your structure, at least 2^63 of them must have a common prefix of 63 bits, by the pigeonhole principle |
| 2025-12-02 17:03:11 | → | trickard_ joins (~trickard@cpe-85-98-47-163.wireline.com.au) |
| 2025-12-02 17:03:31 | × | sord937 quits (~sord937@gateway/tor-sasl/sord937) (Quit: sord937) |
| 2025-12-02 17:03:36 | <merijn> | c_wraith: Don't you mean 2^64 - 2^63 must have the same prefix? |
| 2025-12-02 17:03:54 | <merijn> | Wait, I guess that's the same? |
| 2025-12-02 17:04:02 | <c_wraith> | Actually it's way too early for me to trust my ability to do numbers. |
| 2025-12-02 17:04:11 | <merijn> | It's way to late to trust mine :p |
| 2025-12-02 17:04:25 | <merijn> | c_wraith: Logically speaking only 2 keys will share a 2^63 prefix, no? |
| 2025-12-02 17:04:40 | <merijn> | c_wraith: The one where the last bit is 0 and the one where the last bit is 1? |
| 2025-12-02 17:04:44 | → | Enrico63 joins (~Enrico63@host-212-171-79-170.pool212171.interbusiness.it) |
| 2025-12-02 17:05:15 | × | humasect quits (~humasect@dyn-192-249-132-90.nexicom.net) (Remote host closed the connection) |
| 2025-12-02 17:05:18 | <c_wraith> | I think you're right. But it does mean *some* comparison will take time has a lower bound determined by the number of distinct keys. that's the part I was looking for. |
| 2025-12-02 17:05:21 | <merijn> | 2^63 share a 1 bit prefix :p |
| 2025-12-02 17:05:24 | <haskellbridge> | <loonycyborg> I'm not sure why it matters what they share, they all had to be compared anyway for things to be correct :P |
| 2025-12-02 17:06:03 | <merijn> | It's also not true, since integers aren't compared 1 bit at a time :p |
| 2025-12-02 17:06:17 | <c_wraith> | Which is why I usually talk about strings instead of integers |
| 2025-12-02 17:06:43 | <c_wraith> | because that's when it actually is possible for n to go to infinity anyway |
| 2025-12-02 17:06:58 | <c_wraith> | (we're still pretending we have infinite memory) |
| 2025-12-02 17:09:05 | <haskellbridge> | <loonycyborg> Though it can be hard to picture everything that happens at low level |
| 2025-12-02 17:09:06 | <haskellbridge> | <loonycyborg> cpu adds lots of own optimizations too |
| 2025-12-02 17:09:07 | <haskellbridge> | <loonycyborg> in some cases things might be even free but you'd need to know details very well to take advantage of that |
| 2025-12-02 17:10:26 | <__monty__> | Clearly we need to approach JavaScript's tiny dependency culture. |
| 2025-12-02 17:11:06 | <haskellbridge> | <loonycyborg> Like modern cpus have lot of redundant execution units but not all code ends up using them to the full. |
| 2025-12-02 17:11:26 | <merijn> | __monty__: No, we should have "tiny dependency with minimal transitive footprint" unlike JS which is "tiny dependency with massive transitive footprint" :p |
| 2025-12-02 17:12:24 | <__monty__> | We're limited in our footprints by the unique dependency constraint at least. |
| 2025-12-02 17:12:26 | <haskellbridge> | <loonycyborg> You can have small transitive footprint only if most widely used things (like containers and unordered-containers) are in base |
| 2025-12-02 17:12:55 | <__monty__> | (I'm a base minimalist.) |
| 2025-12-02 17:13:38 | × | kuribas quits (~user@ip-188-118-57-242.reverse.destiny.be) (Remote host closed the connection) |
| 2025-12-02 17:17:12 | <dutchie> | containers is a dependency of the ghc library so I guess it's pretty much everywhere |
| 2025-12-02 17:17:20 | <dutchie> | ( https://downloads.haskell.org/ghc/9.12.1/docs/users_guide/9.12.1-notes.html#included-libraries ) |
| 2025-12-02 17:18:18 | → | Inline joins (~inlinE@2001-4dd3-7fc8-0-434a-a4b1-7362-b14b.ipv6dyn.netcologne.de) |
| 2025-12-02 17:18:58 | × | merijn quits (~merijn@77.242.116.146) (Ping timeout: 255 seconds) |
| 2025-12-02 17:19:54 | → | tromp joins (~textual@2001:1c00:3487:1b00:40c9:191b:e4f:324a) |
| 2025-12-02 17:20:01 | → | vanishingideal joins (~vanishing@user/vanishingideal) |
| 2025-12-02 17:29:17 | <fgarcia> | yes i think work has gone into compilers to get them to detect and optimize for emberassingly parallel operations. some things are difficult to do that for so there will still be a longer wait for some tasks |
| 2025-12-02 17:33:08 | → | peterbecich joins (~Thunderbi@172.222.148.214) |
| 2025-12-02 17:37:49 | → | LooksForFuture joins (~LooksForF@5.74.168.135) |
| 2025-12-02 17:37:55 | × | gawen quits (~gawen@user/gawen) (Quit: cya) |
| 2025-12-02 17:38:36 | <LooksForFuture> | Good resources for learning Haskell for a C programmer? |
| 2025-12-02 17:39:33 | × | LooksForFuture quits (~LooksForF@5.74.168.135) (Client Quit) |
| 2025-12-02 17:40:59 | → | weary-traveler joins (~user@user/user363627) |
| 2025-12-02 17:42:34 | × | Enrico63 quits (~Enrico63@host-212-171-79-170.pool212171.interbusiness.it) (Quit: Client closed) |
| 2025-12-02 17:43:47 | → | gawen joins (~gawen@user/gawen) |
| 2025-12-02 17:51:17 | × | ttybitnik quits (~ttybitnik@user/wolper) (Remote host closed the connection) |
| 2025-12-02 17:51:36 | → | target_i joins (~target_i@user/target-i/x-6023099) |
| 2025-12-02 17:51:47 | <absentia> | LooksForFuture: patience |
| 2025-12-02 17:51:56 | <absentia> | he's definitely a zoomer |
| 2025-12-02 17:53:16 | → | user363627 joins (~user@user/user363627) |
| 2025-12-02 17:54:03 | <mauke> | gotta be quick when looking for the future |
| 2025-12-02 17:54:47 | × | weary-traveler quits (~user@user/user363627) (Ping timeout: 250 seconds) |
| 2025-12-02 17:59:01 | → | ttybitnik joins (~ttybitnik@user/wolper) |
| 2025-12-02 18:02:47 | × | tromp quits (~textual@2001:1c00:3487:1b00:40c9:191b:e4f:324a) (Quit: My iMac has gone to sleep. ZZZzzz…) |
| 2025-12-02 18:03:33 | × | vanishingideal quits (~vanishing@user/vanishingideal) (Remote host closed the connection) |
| 2025-12-02 18:05:54 | × | yin quits (~zero@user/zero) (Ping timeout: 260 seconds) |
| 2025-12-02 18:08:55 | → | yin joins (~zero@user/zero) |
| 2025-12-02 18:11:14 | → | merijn joins (~merijn@host-vr.cgnat-g.v4.dfn.nl) |
| 2025-12-02 18:11:49 | → | ljdarj joins (~Thunderbi@user/ljdarj) |
| 2025-12-02 18:16:30 | × | merijn quits (~merijn@host-vr.cgnat-g.v4.dfn.nl) (Ping timeout: 252 seconds) |
| 2025-12-02 18:16:34 | → | tromp joins (~textual@2001:1c00:3487:1b00:40c9:191b:e4f:324a) |
All times are in UTC.