17 ms·

Criticizing Hare language approach for generic data structures

151 points by ayende 4y ago

formerly_proven 4y ago
"Bring your own datastructures" is likely one of the C carry-overs for Hare. If you think about many "classic" C applications, a lot of them basically only exist around/for one or a few data structures (e.g. most servers, many utilities etc.). In that context BYODS is somewhat defensible: If you don't care to implement the data structure, why does your application exist in the first place? But that's not "modern" applications, which often deal with a ton of data structures. C applications that do so usually have a few "template headers" lying around (indeed, certain operating systems ship with them), though one of the most frequently used data structures in C is of course the intrusive linked list. Which is not a good data structure to use in most cases. Why is it used so much in C? Because it is easiest to implement. Why does that matter? Because C makes implementing generic data structures tedious. Is it a good idea to replicate that model? qed.
- ddevault 4y ago
  Most application's bottlenecks are not their linked lists, and optimizing for anything other than your bottleneck is not the wisest use of your time. Performance is a budget, and I feel comfortable spending some of that budget on simplicity.
  - dathinab 4y ago
    but maps are simpler to use (if appropriately provided by the language). maps/sets are also fundamentally building blocks for a lot of algorthms and structures, not having them makes it WAY harder to implement them. actually potential impossible as performance can easily degrade to a point where it's unusable when you use O(n) (or worse) lookups instead of O(1) ones. this is not a case of premature optimizations but of missing fundamental building blocks and if you don't want genetics, ok, do it like go did initially make the map special language thingy.
  - ayende 4y ago
    Linked list has a O(N) search time, which is atrocious. A really common optimization is to replace a linear scan on a list with a hash table. In most languages, that is a trivial step to do, which means that it gets done. There isn't any overhead. With hare, you just blew your complexity budget on this thing.
    - ddevault 4y ago
      It's not atrocious unless you need the performance. A linked list with a hundred items which is scanned every 90 seconds or something does not really demand attention for optimization, but it will be simpler, easier to write, easier to understand, and easier to debug, and those are wins are not to be sniffed at. And for the record, Hare does have built-in growable slices, so linked lists are pretty rare in Hare. They exist in a few niche situations -- I only ever wrote a Hare program with linked lists once.
      - BaculumMeumEst 4y ago
        Do you remember what the reason that you went with a linked list in that case? I’ve been learning hare and was curious about where to use them. Also, did you use a nullable pointers to represent the next node element in the linked list? Or a tagged union of ( ptr | void)? Or something else?
        ddevault 4y ago
        Yep. I used it in a kernel to create a linked list of statically allocated data structures in a context where dynamic allocation was off the table. You can see the code here: https://git.sr.ht/~yerinalexey/carrot/tree/master/item/console/sifive.ha#L100-125 https://git.sr.ht/~yerinalexey/carrot/tree/master/item/conso... Went with nullable pointer types, which is also a rarely used feature in Hare.
        BaculumMeumEst 4y ago
        Cool, thanks for the link and info
  - usefulcat 4y ago
    Linked lists have generally awful cache locality. If linked lists are not the bottleneck, it's because they already aren't being used for anything where performance matters (which is generally as it should be).
- MrBuddyCasino 4y ago
  BYOD combined with "we don't need a package manager" sounds like a particularly bad combination. I understand Rust's "small stdlib but great package ecosystem", but whats the appeal of "anemic stdlib plus no package ecosystem"? Maybe I would come up with something like this if I only ever worked on Linux software using C, but outside those niches these choices seem weird.
  - orthoxerox 4y ago
    > but whats the appeal of "anemic stdlib plus no package ecosystem"? You can declare your language feature complete sooner
  - capableweb 4y ago
    Correct me if I'm wrong, but Hare doesn't say "we need no package manager" but instead "we don't need a new package manager, use the one your OS provides", at least from how I understand it.
    - mumblemumble 4y ago
      That strikes me as another C-ism that didn't deserve to be carried forward into a 21st century language. There's a reason we call it "dependency hell" and not "happy fun fussing with dependency version conflicts among projects that are completely unrelated except that you happen to be using the same computer to work on them time."
      - steaminghams 4y ago
        The state of the art in package management could be considered Nix and Guix and those are both operating system level package managers and thats why they are better than npm or pypi or cargo, as the aforementioned language specific package managers _dont_ handle dependency hell as native dependencies exist. they all have the same problem as 'they work on my computer' and also encourage this ecosystem of thousands of micropackages, which in a thread so focused on security seems a little ironic given there is no way to guarantee all of those dependencies are made by good actors without a lot of vetting that just is not happening.
- one-more-minute 4y ago
  Rust and Go seemed to initially want to target C programmers [1], but ended up capturing users from higher level languages – even Python and such – who wanted better performance and more control, because they had so many affordances. Hare clearly isn't like that: it's _actually_ aimed at (FOSS) C programmers, almost stubbornly so, and isn't going to appeal to many others. But for those people I can see C-with-tagged-unions being an improvement, and there's value in finding the minimal diff that makes a language better. [1] Remember when Go called itself a "systems programming language"? Neither community seems to use this phrase any more, though.
  - celeritascelery 4y ago
    Rust still considers itself a “systems programming language” . They are moving Rust into the Linux kernel and android drivers. It doesn’t get any more “systems programming” then that. But you are correct about go, it doesn’t give the programmer enough control to be used at that level.
    - 0des 4y ago
      - capableweb 4y ago
        I have no fists in this fight, but wanted some clarification. Are you saying the reason Rust is now being integrated into the Kernel instead of Golang is because of the success of evangelists, not because of the merit of the language itself? I'm not involved in Kernel development myself, but if I was, I'd see your statement as a big hit in the face that we don't know what we're doing, if they (Kernel developers) are being sold to use Rust because of marketing, not because of the value of the language.
        0des 4y ago
        Its not existing kernel devs that suddenly switched to rust. It is the incoming cohort.
- wheelerof4te 4y ago
  "Because C makes implementing generic data structures tedious. Is it a good idea to replicate that model?" A lot of so called "modern" languages make a choice for you. Here is a hash map, over there is a class, have a tuple, set, etc. And they all have a specific way to be used. In implementing all that, many languages lose on flexibility while gaining general utility. Hare seems to go in the opposite direction, one that makes programmers think hard about the solutions to their problems. And that is, IMHO, a good thing.
  - Doxin 4y ago
    I think the main thing is that e.g. python allows you to reimplement all of its most basic data structures in python if you so desire. There's no real way to reimplement e.g. an array in C. The result being that python could still be useful if it wouldn't come with a bunch of data structures built-in.
thecompilr 4y ago
That reminds me that I had to reimplement basic hashmaps in C at least three times in my career. What a waste of time.
- turminal 4y ago
  How much time did you waste?
  - thecompilr 4y ago
    I don't recall exactly, but at least a day each I would say? They were all performance critical, so had to put some effort. Two of them were for internal nginx patches, but were storing data a bit differently so code couldn't be quite reused. In languages with generics hashmaps are trivial to reuse with zero performance cost.
    - JonChesterfield 4y ago
      Is there one with enough parameterisation to choose between different hash collision / resizing / data layout choices? Or one where the various tree/trie/vector alternatives can be swapped in? Seems possible to write such, but std::unordered_map doesn't have it. Maybe rust?
      - thecompilr 4y ago
        Yes, Rust with const generics could probably do that, but I am not aware of an existing implementation.
- gradschool 4y ago
  Was there a good reason not to use Judy arrays?
  - edflsafoiewq 4y ago
    Why would writing a Judy array three times have been better? Aren't they infamously difficult to implement?
bjarneh 4y ago
guerrilla 4y ago
What's the problem? People will just use libraries. Why does it need to be part of the base language? Seems like that made C++ quite a mess in fact, while NPM-like ecosystems have done well.
- edflsafoiewq 4y ago
  > And the design of the Hare language doesn’t even allow me to provide that as a library. I have to fall down to code generation at best.
  - sedeki 4y ago
    How is it possible that the design of a language do not allow for external code/libraries?
    - ayende 4y ago
      The issue is _generic_ data structures, not external code. If I have to re-create a hash table for each scenario, I'll not invest the proper time to do so. So if I need a hash table to map inodes to strings and another to map strings to IP addresses, I'll need to create that anew each time. That means either writing a lot of code twice, or relying on manual code generation (which sucks for many reasons).
      - sedeki 4y ago
        Right, I take my question back
    - rootlocus 4y ago
      No support for generics or custom allocators, combined with no desire to implement a package manager. The language author accepts that (1) Hare is just as limited as C and (2) C has no way of implementing a good hash map. > Recall that Hare is designed to be similar to C in terms of scope and goals. C also provides no general-purpose hash map, and little by way of other data structures (though some attempts exist, none of them good). So you're stuck using a crappy general-purpose hash map that you have to convince your linux distribution package managers to maintain.
rieTohgh6 4y ago
TreeMap as a fallback for bucket and/or some king of random salt for hashes had to be introduced due to security issues (DoS) - I doubt anybody would remember about such stuff when making own hashmap implementation.
- eatonphil 4y ago
  Any links to learn more?
  - formerly_proven 4y ago
    The average performance of hashtables generally depends on collisions being rare, but if the hashed index is trivially derivable from the key, then an attacker can supply data where everything hashes to the same index, regressing performance to the point that it's a DoS attack. This is why cryptographically secure short-output hash functions like SipHash were developed.
  - ddevault 4y ago
    https://en.wikipedia.org/wiki/Collision_attack#Hash_flooding https://en.wikipedia.org/wiki/Collision_attack#Hash_flooding Note that this is only a problem when an attacker can influence your hash table usage, and can be mitigated with hashing functions like siphash. This is not necessary for the majority of hash tables in the wild.
ddevault 4y ago
Thanks for writing this up, though I feel that it may be a bit premature since at this point hardly anyone has any real experience writing Hare code. Regardless, I understand that this is a contentious design decision of Hare, so I would be happy to explain in it in more detail. We have discussed adding first-class maps to the language many times. We recognize the value in this feature and have tried to come up with a good way of doing it that fits within the design constraints of the language, but it has several design issues. There are three key problems: finding a good way of hashing arbitrary data structures (or arbitrarily limiting the kinds of keys the map can store), finding a good way of determining equality of arbitrary data structures, and dealing with memory allocation semantics. Hare does not have generics, and the alternative is a hands-free approach to hashing and equality, which has some troubling limitations, some of which are very unintuitive and non-obvious (which conflicts with our values for explicitness). The allocation problem is also troublesome: Hare uses manual memory management, and any hash map solution which involves magic behind-the-scenes allocations has serious design conflicts with Hare's principles. This article criticizes a sample of a hash map implemented for the build driver. This hash map is used to store a mapping of module details keyed on the module's namespace. It is true that it is a fixed size map, and that collisions can easily be found for the fnv32 hash. These constraints limit the ability for this hash map design to generalize. However, this is not supposed to generalize. It's designed to be a special-purpose hash map for this specific use-case, and takes the simplest approach which is sufficient to this specific problem. As the author notes, there are many approaches to hash maps and there is no one-size-fits-all solution. So far as hash collisions are concerned, these are very unlikely in this use-case. This is not a hash map where hash flooding is a concern, and accidental collisions are so unlikely as to be a negligible risk. If this were not the case, it is easily fixed by just comparing each bucket entry by the namespace rather than by the hash. For use-cases where these things do matter, I would be interested in seeing something like siphash end up in the Hare standard library. Recall that Hare is designed to be similar to C in terms of scope and goals. C also provides no general-purpose hash map, and little by way of other data structures (though some attempts exist, none of them good). Each of these approaches and concerns comes with different needs and trade-offs, and Hare places responsibility for evaluating these needs and trade-offs into the capable hands of the programmer. This is a reflection of Hare's values, which are distinct from the values of some other languages mentioned in the OP - Rust, Go, Zig, C++, etc. Thanks for providing me the opportunity to clarify this here, though perhaps this merited a blog post rather than an overlong HN comment. I understand that this is a design decision which appears especially confusing from the outside, but know that it was made through careful deliberation and discussion. Oh-- and a map-like thing for net::uri would be nice to have as a convenience function in the future. We need to implement the basic approach using the most fundamental design and then build the convenience on top of it, in order to accommodate all use-cases and leave the trade-offs for the user to make.
grnmamba 4y ago
The primary reason I prefer working in C++ over C is that, for all of C++'s faults, it ships with a solid collection of containers and algorithms in the standard library. unordered_map may suck compared to other implementations, but it's a vast improvement over linked lists or home-grown hashmaps. Anyone can write a hash map, in the same way that anyone can write an HTTP server over a weekend. Doesn't mean it will be production quality. Glibc's obstack doesn't count, it's non-standard and the only type it supports is (of course) void*, which is a bad interface.
- veltas 4y ago
  > it's a vast improvement over linked lists or home-grown hashmaps. One of the easiest things to do is write home-grown hashmaps that perform better than std::unordered_map. I suppose you have to worry more about technical debt / bugs, but yes home-grown hashmaps are feasible and I don't think std::unorderd_map is a "vast improvement".
  - ahmedalsudani 4y ago
    Easy to write, sure. But every time a developer has to look at it for the first time, they'll need to learn this hashmap's interface. Do I need to manage memory? Does it manage memory? How do I iterate? How do I add a new key space without thrashing the original implementation and making it twice as complicated? That's the biggest thing a standard interface gives you. Even if it's less performant and not well-designed, I'll take it. The C++ containers are actually well-designed and performant so it's a no-brainer if you get to choose. Almost forgot the type checking you get with C++. That's also a major factor.
    - veltas 4y ago
      I agree with all your points except "are actually well-designed and performant". I mean they perform well enough but when I write simple hashmaps that perform better than libstdc++ (yes with the same hash) anecdotally I don't have a lot of confidence.
newaccount2021 4y ago
nynx 4y ago
It’s unfortunate that people are trying to revive a better version of the past, when the world has moved on and the past ultimately really wasn’t that great. C is a terrible language for building things in the modern world. Not including the progress over the last 4 decades in your new language is a mistake.
- hypeatei 4y ago
  Agreed, I don't know how writing anything in C today would be considered a productive use of time besides low level / embedded work.
  - nynx 4y ago
    Even in the embedded world, it’s becoming less justifiable to use C when your platform supports rust.
    - mh7 4y ago
      rust doesn't offer much value for embedded (mcu, bare metal, tiny stuff) imo. No allocation = no leaks, no use after free, no dangling pointers. No multi core = no atomics or concurrency to worry about. Ring buffers solve 99% of my interrupt data sharing = no need to worry about synchronization. Bounds/safety checks? Need to run and test release builds most of the time because of space/memory constraints.
      - nynx 4y ago
        Rust absolutely benefits embedded software. A big reason is that the type system allows libraries to let you enforce invariants at compile time. For example, your i2c controller only supports two specific pins and they have to be in a specific mode? That can be a compile error if you make a mistake.
        allanparthore 4y ago
        Configuring pins and peripherals with code is a chore, I use graphical tools for that. But C has no problems abstracting away peripherals, just hide the register bits in a private TU and expose i2c_init(), i2c_write(), etc.
duped 4y ago
It's easy to flame young language projects, I don't find that compelling. I don't find the original description compelling either but that's not to say there won't be some kind of support for generic programming or correct hash tables in their standard library (with all the bells and whistles that you need, like randomized insertion order, reasonably fast performance, perhaps optimization for ordinal keys like a btree). What does throw me off about some language projects is the rejection of "complexity" either in a compiler implementation or language feature because it is "complex" - despite decades of research and experience in other languages that some of those features are actually super useful (and also ways to get them wrong or right!). I'm not sure if this is where Hare has landed on generic programming, but it's an ethos I see in a lot of "C but not C" languages that I don't think is a sound approach to language design.
roxaaaane 4y ago
It's 2022
_trackno5 4y ago
I don't get this guy. He's just raging. I agree a hashmap is not simple and Hare's post is a bit naive, but I don't get what's his problem with the language not providing a default implementation. It's part of the language's design. It's targeting people that most likely won't need a hash table. It's not aiming to be a high-level batteries-included language like Java.
- MattPalmer1086 4y ago
  I've been doing some work in C for the first time in a long time. I'm constantly going back to Java to try things out, just because of the absence of convenient data structures. It's a pain to keep recreating them unless it's necessary.
- AshamedCaptain 4y ago
  I think that even the mere fact that there are a billion implementations of a hashmap kind of implies that a hash table _is_ a simple data structure, that you may complicate in a bazillion ways in order to cater for some specific usecase / requeriment. But at it's core, a simple data structure.
  - Chris2048 4y ago
    Why assume that? The specific points in the post appear to be common to all implementations: implementing hashing for example.
  - _trackno5 4y ago
    Fair point. I agree with you on that.
- remus 4y ago
  Maybe it's just the problems I work on and the code I write, but I use hash maps all over the place. Having to write my own sounds like a total pain in the ass, it'll almost certainly not be as performant and/or have some subtle bugs to figure out. I guess Im not the target audience for the language, but the lack of basic data structures like this adds a lot of friction for me.
dathinab 4y ago
it can't be understated how insanely hard it is to get maps right and that not getting them right (e.g. not having them or problematic implementations) is prone to produce subtle security vulnerabilities in large projects. Most times DoS attack vector not cought by normal (D)DoS protection (especially with micro services they can be nasty).
flohofwoe 4y ago
This reads like a rant of a person caught too much in their own bubble, a bubble in which hash maps seem to be of extreme importance. I've coded a lot of C in the past few years, and I can count the number of times when I would have actually needed a proper high performance hash map with all bells and whistles on one hand. A piece of code where hash map lookups are so frequent that it becomes a performance bottleneck is either badly designed, or a special case which needs a very careful implementation. Builtin hash maps are convenient for "dictionary languages" like Python or Javascript, but beyond that they are highly specialized and tailored to specific data sets and hardware properties.
- carapace 4y ago
  I knew a guy who only used PHP (and a little JS) and he literally did not know the difference between hash maps, linked lists, and arrays. The SOB is a millionaire now.
- BitterAmethyst 4y ago
  The author writes database engines.
thrower123 4y ago
We seem to be very worked up over a virtually unknown new C-replacement language that's more likely than not to fizzle and become yet another 0.1% also-ran.
- ATsch 4y ago
  I feel like people are less getting worked up over Hare itself, and more what it represents. It is very much a reactionary language, defined less by any grand new ideas or visions and more by rejection of things that many people see as valuable progress over the last few decades. It doesn't help that it is being pushed by an already highly notable and controversial figure. The language just happens to be a convenient vehicle for arguing about these engineering (and personal) values.
tialaramex 4y ago
Yesterday, while reading about Hare, I discovered the problem this blog post alludes to (Hare's own module code just assumes if the hash for two modules was identical, they're the same module) and I reported it to Hare's developer list. https://lists.sr.ht/~sircmpwn/hare-dev/%3C20220503143516.19e61ad8%40totoro.tlrmx.org%3E https://lists.sr.ht/~sircmpwn/hare-dev/%3C20220503143516.19e... I was sort of expecting Drew to... fix it? I mean, what you'd hope for is an updated blog post with a mea culpa in it, but I'm not setting my expectations so high. Fixing the bug seems like a pretty basic place to start though.
- ddevault 4y ago
  Thanks for the email - yours is one of 46 emails in my Hare queue, which is why it has not been addressed yet. I agree with your comments and have filed a ticket to address them, however, and I will answer your email in time. Thanks for your patience!
urschrei 4y ago
Is it too late to rename the language to Ostrich?
socialdemocrat 4y ago
Why do people spend so much energy shooting down a language nobody uses? If you don’t like it you don’t have to use it. I would hate to be the creator of Hare and get so much crap for simply daring to exist. He is making a language he likes and wants to use. There are probably some people who like it and find it useful. Good for them! A lot of us have dreams of building our own language. He is following his passions and people are just lining up to be Debbie Downers. Now I almost feel like I need to learn more Hare to give the guy some encouragement and positive feedback on things done right. Be the glass half full guy. Well I won’t. I think Zig will be the last C-like language I invest time in. It is so easy to get sucked into something new that will never go mainstream.
- jolux 4y ago
  We don’t need more memory-unsafe languages with no generics and no functional programming. We just don’t. If it were a toy project for learning and pedagogical purposes that’s one thing but for code that’s supposed to be used in production it’s useless.
  - amelius 4y ago
    Not sure what you mean. Rust has no functional programming either ...
    - jolux 4y ago
      Functional programming patterns are very common in Rust code. It doesn’t have automatic currying or higher-kinded types but it has generic associated types, anonymous functions, closures, and a rich set of collections with functional processing methods in the standard library.
      - capableweb 4y ago
        A lot of the standard library and an extensive part of the community ecosystem lives and breathes mutation at both the edges and in the internals, something people normally would avoid when trying to stick with functional programming. Sure, some mutation is always needed, but Rust wouldn't be the first language I'd pick if I want to focus on functional programming for sure.
fbanon 4y ago
Sounds a bit... hare-brained. :^)
jordemort 4y ago
I'm so bored with all this reactionary tech. I don't understand the urge to reinvent everything from first principles while ignoring the last 30 years of advances in computing. I was alive back then. Things weren't actually better.
- bccdee 4y ago
  I think it's simple: People don't want something like Python or Java, which improves on old stuff with a big runtime, and they don't want something like Rust, which improves on old stuff with lots of complicated static checking. You can't write an OS in Python, and Rust isn't simple, which these people really want. So throw away the runtime, throw away the fancy compiler checks, and you just have a slightly nicer C.
specialist 4y ago
My future perfect "practical" programming language will have type inference, strong typing, and intrinsics for misc data structures. In other words, looks kinda like JavaScript, behaves kinda like Java. This: foo = { "apples" : 100, "bananas" : 20 } bar = [ 100, 200, "oops" ] // error Instead of this: foo = new hashmap<string,int> foo.put( "apples", 100 ) foo.put( "bananas", 20 ) bar = new array<int> bar.add( 100 ) bar.add( 200 ) bar.add( "oops" ) // error I believe, but cannot yet prove, this would eliminate 98% of the (popular) pressure (desire for concision) for adding generics.
YeGoblynQueenne 4y ago
Is there any field or subject where people don't routinely take a dump on each other's work? Or am I just being overseinsitive, too easily vexxed?

151 points by ayende 4y ago

"Bring your own datastructures" is likely one of the C carry-overs for Hare. If you think about many "classic" C applications, a lot of them basically only exist around/for one or a few data structures (e.g. most servers, many utilities etc.). In that context BYODS is somewhat defensible: If you don't care to implement the data structure, why does your application exist in the first place? But that's not "modern" applications, which often deal with a ton of data structures. C applications that do so usually have a few "template headers" lying around (indeed, certain operating systems ship with them), though one of the most frequently used data structures in C is of course the intrusive linked list. Which is not a good data structure to use in most cases. Why is it used so much in C? Because it is easiest to implement. Why does that matter? Because C makes implementing generic data structures tedious. Is it a good idea to replicate that model? qed.

ddevault 4y ago
Most application's bottlenecks are not their linked lists, and optimizing for anything other than your bottleneck is not the wisest use of your time. Performance is a budget, and I feel comfortable spending some of that budget on simplicity.
- dathinab 4y ago
  but maps are simpler to use (if appropriately provided by the language). maps/sets are also fundamentally building blocks for a lot of algorthms and structures, not having them makes it WAY harder to implement them. actually potential impossible as performance can easily degrade to a point where it's unusable when you use O(n) (or worse) lookups instead of O(1) ones. this is not a case of premature optimizations but of missing fundamental building blocks and if you don't want genetics, ok, do it like go did initially make the map special language thingy.
- ayende 4y ago
  Linked list has a O(N) search time, which is atrocious. A really common optimization is to replace a linear scan on a list with a hash table. In most languages, that is a trivial step to do, which means that it gets done. There isn't any overhead. With hare, you just blew your complexity budget on this thing.
  - ddevault 4y ago
    It's not atrocious unless you need the performance. A linked list with a hundred items which is scanned every 90 seconds or something does not really demand attention for optimization, but it will be simpler, easier to write, easier to understand, and easier to debug, and those are wins are not to be sniffed at. And for the record, Hare does have built-in growable slices, so linked lists are pretty rare in Hare. They exist in a few niche situations -- I only ever wrote a Hare program with linked lists once.
    - BaculumMeumEst 4y ago
      Do you remember what the reason that you went with a linked list in that case? I’ve been learning hare and was curious about where to use them. Also, did you use a nullable pointers to represent the next node element in the linked list? Or a tagged union of ( ptr | void)? Or something else?
      - ddevault 4y ago
        Yep. I used it in a kernel to create a linked list of statically allocated data structures in a context where dynamic allocation was off the table. You can see the code here: https://git.sr.ht/~yerinalexey/carrot/tree/master/item/console/sifive.ha#L100-125 https://git.sr.ht/~yerinalexey/carrot/tree/master/item/conso... Went with nullable pointer types, which is also a rarely used feature in Hare.
        BaculumMeumEst 4y ago
        Cool, thanks for the link and info
- usefulcat 4y ago
  Linked lists have generally awful cache locality. If linked lists are not the bottleneck, it's because they already aren't being used for anything where performance matters (which is generally as it should be).
MrBuddyCasino 4y ago
BYOD combined with "we don't need a package manager" sounds like a particularly bad combination. I understand Rust's "small stdlib but great package ecosystem", but whats the appeal of "anemic stdlib plus no package ecosystem"? Maybe I would come up with something like this if I only ever worked on Linux software using C, but outside those niches these choices seem weird.
- orthoxerox 4y ago
  > but whats the appeal of "anemic stdlib plus no package ecosystem"? You can declare your language feature complete sooner
- capableweb 4y ago
  Correct me if I'm wrong, but Hare doesn't say "we need no package manager" but instead "we don't need a new package manager, use the one your OS provides", at least from how I understand it.
  - mumblemumble 4y ago
    That strikes me as another C-ism that didn't deserve to be carried forward into a 21st century language. There's a reason we call it "dependency hell" and not "happy fun fussing with dependency version conflicts among projects that are completely unrelated except that you happen to be using the same computer to work on them time."
    - steaminghams 4y ago
      The state of the art in package management could be considered Nix and Guix and those are both operating system level package managers and thats why they are better than npm or pypi or cargo, as the aforementioned language specific package managers _dont_ handle dependency hell as native dependencies exist. they all have the same problem as 'they work on my computer' and also encourage this ecosystem of thousands of micropackages, which in a thread so focused on security seems a little ironic given there is no way to guarantee all of those dependencies are made by good actors without a lot of vetting that just is not happening.
one-more-minute 4y ago
Rust and Go seemed to initially want to target C programmers [1], but ended up capturing users from higher level languages – even Python and such – who wanted better performance and more control, because they had so many affordances. Hare clearly isn't like that: it's _actually_ aimed at (FOSS) C programmers, almost stubbornly so, and isn't going to appeal to many others. But for those people I can see C-with-tagged-unions being an improvement, and there's value in finding the minimal diff that makes a language better. [1] Remember when Go called itself a "systems programming language"? Neither community seems to use this phrase any more, though.
- celeritascelery 4y ago
  Rust still considers itself a “systems programming language” . They are moving Rust into the Linux kernel and android drivers. It doesn’t get any more “systems programming” then that. But you are correct about go, it doesn’t give the programmer enough control to be used at that level.
  - 0des 4y ago
    - capableweb 4y ago
      I have no fists in this fight, but wanted some clarification. Are you saying the reason Rust is now being integrated into the Kernel instead of Golang is because of the success of evangelists, not because of the merit of the language itself? I'm not involved in Kernel development myself, but if I was, I'd see your statement as a big hit in the face that we don't know what we're doing, if they (Kernel developers) are being sold to use Rust because of marketing, not because of the value of the language.
      - 0des 4y ago
        Its not existing kernel devs that suddenly switched to rust. It is the incoming cohort.
wheelerof4te 4y ago
"Because C makes implementing generic data structures tedious. Is it a good idea to replicate that model?" A lot of so called "modern" languages make a choice for you. Here is a hash map, over there is a class, have a tuple, set, etc. And they all have a specific way to be used. In implementing all that, many languages lose on flexibility while gaining general utility. Hare seems to go in the opposite direction, one that makes programmers think hard about the solutions to their problems. And that is, IMHO, a good thing.
- Doxin 4y ago
  I think the main thing is that e.g. python allows you to reimplement all of its most basic data structures in python if you so desire. There's no real way to reimplement e.g. an array in C. The result being that python could still be useful if it wouldn't come with a bunch of data structures built-in.

thecompilr 4y ago

That reminds me that I had to reimplement basic hashmaps in C at least three times in my career. What a waste of time.

turminal 4y ago
How much time did you waste?
- thecompilr 4y ago
  I don't recall exactly, but at least a day each I would say? They were all performance critical, so had to put some effort. Two of them were for internal nginx patches, but were storing data a bit differently so code couldn't be quite reused. In languages with generics hashmaps are trivial to reuse with zero performance cost.
  - JonChesterfield 4y ago
    Is there one with enough parameterisation to choose between different hash collision / resizing / data layout choices? Or one where the various tree/trie/vector alternatives can be swapped in? Seems possible to write such, but std::unordered_map doesn't have it. Maybe rust?
    - thecompilr 4y ago
      Yes, Rust with const generics could probably do that, but I am not aware of an existing implementation.
gradschool 4y ago
Was there a good reason not to use Judy arrays?
- edflsafoiewq 4y ago
  Why would writing a Judy array three times have been better? Aren't they infamously difficult to implement?

bjarneh 4y ago

guerrilla 4y ago

What's the problem? People will just use libraries. Why does it need to be part of the base language? Seems like that made C++ quite a mess in fact, while NPM-like ecosystems have done well.

edflsafoiewq 4y ago
> And the design of the Hare language doesn’t even allow me to provide that as a library. I have to fall down to code generation at best.
- sedeki 4y ago
  How is it possible that the design of a language do not allow for external code/libraries?
  - ayende 4y ago
    The issue is _generic_ data structures, not external code. If I have to re-create a hash table for each scenario, I'll not invest the proper time to do so. So if I need a hash table to map inodes to strings and another to map strings to IP addresses, I'll need to create that anew each time. That means either writing a lot of code twice, or relying on manual code generation (which sucks for many reasons).
    - sedeki 4y ago
      Right, I take my question back
  - rootlocus 4y ago
    No support for generics or custom allocators, combined with no desire to implement a package manager. The language author accepts that (1) Hare is just as limited as C and (2) C has no way of implementing a good hash map. > Recall that Hare is designed to be similar to C in terms of scope and goals. C also provides no general-purpose hash map, and little by way of other data structures (though some attempts exist, none of them good). So you're stuck using a crappy general-purpose hash map that you have to convince your linux distribution package managers to maintain.

rieTohgh6 4y ago

TreeMap as a fallback for bucket and/or some king of random salt for hashes had to be introduced due to security issues (DoS) - I doubt anybody would remember about such stuff when making own hashmap implementation.

eatonphil 4y ago
Any links to learn more?
- formerly_proven 4y ago
  The average performance of hashtables generally depends on collisions being rare, but if the hashed index is trivially derivable from the key, then an attacker can supply data where everything hashes to the same index, regressing performance to the point that it's a DoS attack. This is why cryptographically secure short-output hash functions like SipHash were developed.
- ddevault 4y ago
  https://en.wikipedia.org/wiki/Collision_attack#Hash_flooding https://en.wikipedia.org/wiki/Collision_attack#Hash_flooding Note that this is only a problem when an attacker can influence your hash table usage, and can be mitigated with hashing functions like siphash. This is not necessary for the majority of hash tables in the wild.

ddevault 4y ago

Thanks for writing this up, though I feel that it may be a bit premature since at this point hardly anyone has any real experience writing Hare code. Regardless, I understand that this is a contentious design decision of Hare, so I would be happy to explain in it in more detail. We have discussed adding first-class maps to the language many times. We recognize the value in this feature and have tried to come up with a good way of doing it that fits within the design constraints of the language, but it has several design issues. There are three key problems: finding a good way of hashing arbitrary data structures (or arbitrarily limiting the kinds of keys the map can store), finding a good way of determining equality of arbitrary data structures, and dealing with memory allocation semantics. Hare does not have generics, and the alternative is a hands-free approach to hashing and equality, which has some troubling limitations, some of which are very unintuitive and non-obvious (which conflicts with our values for explicitness). The allocation problem is also troublesome: Hare uses manual memory management, and any hash map solution which involves magic behind-the-scenes allocations has serious design conflicts with Hare's principles. This article criticizes a sample of a hash map implemented for the build driver. This hash map is used to store a mapping of module details keyed on the module's namespace. It is true that it is a fixed size map, and that collisions can easily be found for the fnv32 hash. These constraints limit the ability for this hash map design to generalize. However, this is not supposed to generalize. It's designed to be a special-purpose hash map for this specific use-case, and takes the simplest approach which is sufficient to this specific problem. As the author notes, there are many approaches to hash maps and there is no one-size-fits-all solution. So far as hash collisions are concerned, these are very unlikely in this use-case. This is not a hash map where hash flooding is a concern, and accidental collisions are so unlikely as to be a negligible risk. If this were not the case, it is easily fixed by just comparing each bucket entry by the namespace rather than by the hash. For use-cases where these things do matter, I would be interested in seeing something like siphash end up in the Hare standard library. Recall that Hare is designed to be similar to C in terms of scope and goals. C also provides no general-purpose hash map, and little by way of other data structures (though some attempts exist, none of them good). Each of these approaches and concerns comes with different needs and trade-offs, and Hare places responsibility for evaluating these needs and trade-offs into the capable hands of the programmer. This is a reflection of Hare's values, which are distinct from the values of some other languages mentioned in the OP - Rust, Go, Zig, C++, etc. Thanks for providing me the opportunity to clarify this here, though perhaps this merited a blog post rather than an overlong HN comment. I understand that this is a design decision which appears especially confusing from the outside, but know that it was made through careful deliberation and discussion. Oh-- and a map-like thing for net::uri would be nice to have as a convenience function in the future. We need to implement the basic approach using the most fundamental design and then build the convenience on top of it, in order to accommodate all use-cases and leave the trade-offs for the user to make.

grnmamba 4y ago

The primary reason I prefer working in C++ over C is that, for all of C++'s faults, it ships with a solid collection of containers and algorithms in the standard library. unordered_map may suck compared to other implementations, but it's a vast improvement over linked lists or home-grown hashmaps. Anyone can write a hash map, in the same way that anyone can write an HTTP server over a weekend. Doesn't mean it will be production quality. Glibc's obstack doesn't count, it's non-standard and the only type it supports is (of course) void*, which is a bad interface.

veltas 4y ago
> it's a vast improvement over linked lists or home-grown hashmaps. One of the easiest things to do is write home-grown hashmaps that perform better than std::unordered_map. I suppose you have to worry more about technical debt / bugs, but yes home-grown hashmaps are feasible and I don't think std::unorderd_map is a "vast improvement".
- ahmedalsudani 4y ago
  Easy to write, sure. But every time a developer has to look at it for the first time, they'll need to learn this hashmap's interface. Do I need to manage memory? Does it manage memory? How do I iterate? How do I add a new key space without thrashing the original implementation and making it twice as complicated? That's the biggest thing a standard interface gives you. Even if it's less performant and not well-designed, I'll take it. The C++ containers are actually well-designed and performant so it's a no-brainer if you get to choose. Almost forgot the type checking you get with C++. That's also a major factor.
  - veltas 4y ago
    I agree with all your points except "are actually well-designed and performant". I mean they perform well enough but when I write simple hashmaps that perform better than libstdc++ (yes with the same hash) anecdotally I don't have a lot of confidence.

newaccount2021 4y ago

nynx 4y ago

It’s unfortunate that people are trying to revive a better version of the past, when the world has moved on and the past ultimately really wasn’t that great. C is a terrible language for building things in the modern world. Not including the progress over the last 4 decades in your new language is a mistake.

hypeatei 4y ago
Agreed, I don't know how writing anything in C today would be considered a productive use of time besides low level / embedded work.
- nynx 4y ago
  Even in the embedded world, it’s becoming less justifiable to use C when your platform supports rust.
  - mh7 4y ago
    rust doesn't offer much value for embedded (mcu, bare metal, tiny stuff) imo. No allocation = no leaks, no use after free, no dangling pointers. No multi core = no atomics or concurrency to worry about. Ring buffers solve 99% of my interrupt data sharing = no need to worry about synchronization. Bounds/safety checks? Need to run and test release builds most of the time because of space/memory constraints.
    - nynx 4y ago
      Rust absolutely benefits embedded software. A big reason is that the type system allows libraries to let you enforce invariants at compile time. For example, your i2c controller only supports two specific pins and they have to be in a specific mode? That can be a compile error if you make a mistake.
      - allanparthore 4y ago
        Configuring pins and peripherals with code is a chore, I use graphical tools for that. But C has no problems abstracting away peripherals, just hide the register bits in a private TU and expose i2c_init(), i2c_write(), etc.

duped 4y ago

It's easy to flame young language projects, I don't find that compelling. I don't find the original description compelling either but that's not to say there won't be some kind of support for generic programming or correct hash tables in their standard library (with all the bells and whistles that you need, like randomized insertion order, reasonably fast performance, perhaps optimization for ordinal keys like a btree). What does throw me off about some language projects is the rejection of "complexity" either in a compiler implementation or language feature because it is "complex" - despite decades of research and experience in other languages that some of those features are actually super useful (and also ways to get them wrong or right!). I'm not sure if this is where Hare has landed on generic programming, but it's an ethos I see in a lot of "C but not C" languages that I don't think is a sound approach to language design.

roxaaaane 4y ago

It's 2022

_trackno5 4y ago

I don't get this guy. He's just raging. I agree a hashmap is not simple and Hare's post is a bit naive, but I don't get what's his problem with the language not providing a default implementation. It's part of the language's design. It's targeting people that most likely won't need a hash table. It's not aiming to be a high-level batteries-included language like Java.

MattPalmer1086 4y ago
I've been doing some work in C for the first time in a long time. I'm constantly going back to Java to try things out, just because of the absence of convenient data structures. It's a pain to keep recreating them unless it's necessary.
AshamedCaptain 4y ago
I think that even the mere fact that there are a billion implementations of a hashmap kind of implies that a hash table _is_ a simple data structure, that you may complicate in a bazillion ways in order to cater for some specific usecase / requeriment. But at it's core, a simple data structure.
- Chris2048 4y ago
  Why assume that? The specific points in the post appear to be common to all implementations: implementing hashing for example.
- _trackno5 4y ago
  Fair point. I agree with you on that.
remus 4y ago
Maybe it's just the problems I work on and the code I write, but I use hash maps all over the place. Having to write my own sounds like a total pain in the ass, it'll almost certainly not be as performant and/or have some subtle bugs to figure out. I guess Im not the target audience for the language, but the lack of basic data structures like this adds a lot of friction for me.

dathinab 4y ago

it can't be understated how insanely hard it is to get maps right and that not getting them right (e.g. not having them or problematic implementations) is prone to produce subtle security vulnerabilities in large projects. Most times DoS attack vector not cought by normal (D)DoS protection (especially with micro services they can be nasty).

flohofwoe 4y ago

This reads like a rant of a person caught too much in their own bubble, a bubble in which hash maps seem to be of extreme importance. I've coded a lot of C in the past few years, and I can count the number of times when I would have actually needed a proper high performance hash map with all bells and whistles on one hand. A piece of code where hash map lookups are so frequent that it becomes a performance bottleneck is either badly designed, or a special case which needs a very careful implementation. Builtin hash maps are convenient for "dictionary languages" like Python or Javascript, but beyond that they are highly specialized and tailored to specific data sets and hardware properties.

carapace 4y ago
I knew a guy who only used PHP (and a little JS) and he literally did not know the difference between hash maps, linked lists, and arrays. The SOB is a millionaire now.
BitterAmethyst 4y ago
The author writes database engines.

thrower123 4y ago

We seem to be very worked up over a virtually unknown new C-replacement language that's more likely than not to fizzle and become yet another 0.1% also-ran.

ATsch 4y ago
I feel like people are less getting worked up over Hare itself, and more what it represents. It is very much a reactionary language, defined less by any grand new ideas or visions and more by rejection of things that many people see as valuable progress over the last few decades. It doesn't help that it is being pushed by an already highly notable and controversial figure. The language just happens to be a convenient vehicle for arguing about these engineering (and personal) values.

tialaramex 4y ago

Yesterday, while reading about Hare, I discovered the problem this blog post alludes to (Hare's own module code just assumes if the hash for two modules was identical, they're the same module) and I reported it to Hare's developer list. https://lists.sr.ht/~sircmpwn/hare-dev/%3C20220503143516.19e61ad8%40totoro.tlrmx.org%3E https://lists.sr.ht/~sircmpwn/hare-dev/%3C20220503143516.19e... I was sort of expecting Drew to... fix it? I mean, what you'd hope for is an updated blog post with a mea culpa in it, but I'm not setting my expectations so high. Fixing the bug seems like a pretty basic place to start though.

ddevault 4y ago
Thanks for the email - yours is one of 46 emails in my Hare queue, which is why it has not been addressed yet. I agree with your comments and have filed a ticket to address them, however, and I will answer your email in time. Thanks for your patience!

urschrei 4y ago

Is it too late to rename the language to Ostrich?

socialdemocrat 4y ago

Why do people spend so much energy shooting down a language nobody uses? If you don’t like it you don’t have to use it. I would hate to be the creator of Hare and get so much crap for simply daring to exist. He is making a language he likes and wants to use. There are probably some people who like it and find it useful. Good for them! A lot of us have dreams of building our own language. He is following his passions and people are just lining up to be Debbie Downers. Now I almost feel like I need to learn more Hare to give the guy some encouragement and positive feedback on things done right. Be the glass half full guy. Well I won’t. I think Zig will be the last C-like language I invest time in. It is so easy to get sucked into something new that will never go mainstream.

jolux 4y ago
We don’t need more memory-unsafe languages with no generics and no functional programming. We just don’t. If it were a toy project for learning and pedagogical purposes that’s one thing but for code that’s supposed to be used in production it’s useless.
- amelius 4y ago
  Not sure what you mean. Rust has no functional programming either ...
  - jolux 4y ago
    Functional programming patterns are very common in Rust code. It doesn’t have automatic currying or higher-kinded types but it has generic associated types, anonymous functions, closures, and a rich set of collections with functional processing methods in the standard library.
    - capableweb 4y ago
      A lot of the standard library and an extensive part of the community ecosystem lives and breathes mutation at both the edges and in the internals, something people normally would avoid when trying to stick with functional programming. Sure, some mutation is always needed, but Rust wouldn't be the first language I'd pick if I want to focus on functional programming for sure.

fbanon 4y ago

Sounds a bit... hare-brained. :^)

jordemort 4y ago

I'm so bored with all this reactionary tech. I don't understand the urge to reinvent everything from first principles while ignoring the last 30 years of advances in computing. I was alive back then. Things weren't actually better.

bccdee 4y ago
I think it's simple: People don't want something like Python or Java, which improves on old stuff with a big runtime, and they don't want something like Rust, which improves on old stuff with lots of complicated static checking. You can't write an OS in Python, and Rust isn't simple, which these people really want. So throw away the runtime, throw away the fancy compiler checks, and you just have a slightly nicer C.

specialist 4y ago

My future perfect "practical" programming language will have type inference, strong typing, and intrinsics for misc data structures. In other words, looks kinda like JavaScript, behaves kinda like Java. This: foo = { "apples" : 100, "bananas" : 20 } bar = [ 100, 200, "oops" ] // error Instead of this: foo = new hashmap<string,int> foo.put( "apples", 100 ) foo.put( "bananas", 20 ) bar = new array<int> bar.add( 100 ) bar.add( 200 ) bar.add( "oops" ) // error I believe, but cannot yet prove, this would eliminate 98% of the (popular) pressure (desire for concision) for adding generics.

YeGoblynQueenne 4y ago

Is there any field or subject where people don't routinely take a dump on each other's work? Or am I just being overseinsitive, too easily vexxed?