Newest at the top
| 2025-11-13 12:21:20 +0100 | <lucabtz> | [exa] yeah i didnt think of that, though it wouldnt work, what about hash collisions? |
| 2025-11-13 12:19:52 +0100 | <[exa]> | lucabtz: like at wurst you can commit a heinous crime and order by the hash. Not sure if the other ways is doable universally tho. |
| 2025-11-13 12:17:48 +0100 | <merijn> | (important side note that containers indeed guarantees that foldable/traversable operation happen in ascending key order) |
| 2025-11-13 12:17:47 +0100 | <lucabtz> | so it isnt very different |
| 2025-11-13 12:17:42 +0100 | <lucabtz> | but you need a hash in the hash map |
| 2025-11-13 12:17:32 +0100 | <lucabtz> | though you need ordering for a tree map which you dont for a hash map |
| 2025-11-13 12:17:15 +0100 | <[exa]> | <3 |
| 2025-11-13 12:17:11 +0100 | <merijn> | <3 |
| 2025-11-13 12:17:09 +0100 | <merijn> | Guaranteed stable ordering for traversals/iteration too |
| 2025-11-13 12:17:04 +0100 | <lucabtz> | merijn yeah yeah your point is valid |
| 2025-11-13 12:16:48 +0100 | <merijn> | Additionally the ability of ordered maps to look up "smallest key bigger than X" or "smallest key larger than X" is super useful in many situations. |
| 2025-11-13 12:16:12 +0100 | <merijn> | 20-30% more space than you have data |
| 2025-11-13 12:16:06 +0100 | <merijn> | lucabtz: A decent tree implementation like red-black or AVL tree guarantee O(log n) worst case lookup and insert (vs O(n) worst case for hashmap). Now hashmap can have better average case, but that depends on the ratio of keys to buckets. You need a certain percentage of empty buckets to avoid collissions, I don't know the optimal numbers but I'm betting at least 20-30%. So that means you must allocate |
| 2025-11-13 12:15:50 +0100 | <[exa]> | kuribas`: anyway the most formal argument against the hashmaps that I have is literally that cache bump that you saw there in the benchmarks. With hashmaps it's unavoidable if your map grows; with sensible maps you can make it disappear using some kind of locality on a map of any size. |
| 2025-11-13 12:13:11 +0100 | <[exa]> | doc: no that's embedding_vector_map, that was popular 3 years ago. Behold: `insertAiMap k v = unsafePerformGemini $ "Please remember that " ++ show k ++ " saves " ++ show v` |
| 2025-11-13 12:12:54 +0100 | <merijn> | doc: I mean, replace the hashmap with a metric tree and that's actually neat |
| 2025-11-13 12:12:46 +0100 | <lucabtz> | merijn im a C++ developer as day job and always hated that std::map is not a hashmap but you are making me reconsider |
| 2025-11-13 12:12:24 +0100 | <haskellbridge> | <doc> i am sure that has gone through a couple hype cycles already |
| 2025-11-13 12:11:41 +0100 | <haskellbridge> | <doc> ai_map.. now that's just a hashmap where everything is hashed to embedding vectors :^) |
| 2025-11-13 12:11:27 +0100 | <[exa]> | merijn: I told them they failed me, don't worry. :D |
| 2025-11-13 12:10:55 +0100 | <[exa]> | anyway yeah the unordered wording is great there, tells nicely which property is lost |
| 2025-11-13 12:10:46 +0100 | <merijn> | [exa]: Fail them! |
| 2025-11-13 12:10:36 +0100 | <[exa]> | merijn: I saw stuff like `using map = std::unordered_map;` from students, wasn't happy |
| 2025-11-13 12:10:29 +0100 | Taneb | (~username@host-95-251-57-201.retail.telecomitalia.it) (Ping timeout: 256 seconds) |
| 2025-11-13 12:10:19 +0100 | <merijn> | The only reason I'm not a professional SQLite shill is that I haven't figured out how to get paid :p |
| 2025-11-13 12:09:43 +0100 | <[exa]> | ...at which point the cool thing is gonna be std::ai_map or so |
| 2025-11-13 12:09:24 +0100 | <[exa]> | kuribas`: tbh you should start professionally hating hashmaps just for the purpose of being cool way before it becomes popularly cool in 20 years from now |
| 2025-11-13 12:09:00 +0100 | <merijn> | I also strongly approve C++ have std::map be a sensible map and requiring people to write std::unordered_map to get a hashmap |
| 2025-11-13 12:08:09 +0100 | <merijn> | IMO the fact that containers only ships tree maps is absolutely based and helps default people to a good map type |
| 2025-11-13 12:07:29 +0100 | <[exa]> | I already said "over-generalized" somewhere right. :D |
| 2025-11-13 12:07:27 +0100 | <merijn> | [exa]: Especially since neither python nor JS give you easy access to non-hashmaps, people just pretend non hashmaps don't exist. |
| 2025-11-13 12:06:52 +0100 | <merijn> | [exa]: JavaScript and Python popularised the use of maps. They use hashmaps, people get taught maps using the word hashmap. People internalise "hashmap good" |
| 2025-11-13 12:06:20 +0100 | [exa] | sad |
| 2025-11-13 12:06:02 +0100 | <[exa]> | like, there are great applications of hashes that actually make sense, like bloom filters and whatnot, why does everyone want hashmaps? |
| 2025-11-13 12:05:03 +0100 | ezzieyguywuf | (~Unknown@user/ezzieyguywuf) (Ping timeout: 250 seconds) |
| 2025-11-13 12:03:55 +0100 | trickard_ | trickard |
| 2025-11-13 12:03:21 +0100 | <[exa]> | kuribas`: then you go patricia trees and/or precompiled string matchers (aho-corasick style) |
| 2025-11-13 11:59:49 +0100 | <kuribas`> | right :) |
| 2025-11-13 11:59:38 +0100 | <[exa]> | kuribas`: anyway you might have notice that you hit 2 professional hashmap haters today |
| 2025-11-13 11:59:34 +0100 | <kuribas`> | [exa]: what if I care about time more than space? |
| 2025-11-13 11:59:25 +0100 | <merijn> | https://sqlite.org/stricttables.html |
| 2025-11-13 11:59:13 +0100 | <merijn> | kuribas`: Have you not heard the glorious news of SQLite STRICT mode? :p |
| 2025-11-13 11:58:40 +0100 | <[exa]> | kuribas`: no it requires a trie, hashmaps waste space for interning |
| 2025-11-13 11:58:34 +0100 | <kuribas`> | I have sqlite in my python project, and I feel its just now untyped queries instead of typed data processing... |
| 2025-11-13 11:57:40 +0100 | <merijn> | All I will say is that I've switched to SQLite from whatever I was using 3 times in projects, and every single time I have the same epiphany :p Which is, that I should use more SQLite in everything :p |
| 2025-11-13 11:56:43 +0100 | <kuribas`> | merijn: yeah, but the interning needs another hashmap. |
| 2025-11-13 11:56:22 +0100 | <merijn> | kuribas`: Naah, with interned strings you could just use a tree map, since then [exa] comment about repeated compares goes away :p |
| 2025-11-13 11:55:55 +0100 | <kuribas`> | Sure I can intern all the strings, that would just be another hashmap... |
| 2025-11-13 11:55:44 +0100 | <merijn> | kuribas`: tbh 1) it's probably worth figuring out how to do it in SQLite anyway, 2) if you can turn it into a JSON encoding you can just store (and query) json blobs in SQLite :p |
| 2025-11-13 11:55:29 +0100 | <kuribas`> | and strings for addresses, driver names, device models, etc.. |