"Immutable-js Map Transient" means an Immutable-js Map that uses "withMutations" for extra speed.
I also want to test out ClojureScript's data structures, but I haven't gotten around to it yet.
----
As I said earlier, AVL trees are fast. They tend to be 0-3x slower than JavaScript objects.
Stop and think about that for a moment: JavaScript objects are mutable, they're written in C++, they're heavily optimized with various tricks, and they're probably implemented as hash tables.
Meanwhile, AVL trees are immutable, do not use any kind of optimization tricks (the algorithms are very simple and straightforward), and they are implemented in vanilla JavaScript, in less than 400 lines of code.
JavaScript engines are fast. So fast that immutable AVL trees are completely viable. I would not hesitate to replace all my programs with them. This is quite amazing.
In addition, notice that according to those benchmark numbers, you can create 20 empty AVL trees, then insert 100 keys into each AVL tree (for a total of 2,000 insert operations)... once per millisecond. In this case, worrying about the performance cost of immutability is a huge premature optimization.
(I'm not directing this at anybody in particular, in fact I am the kind of person that does premature optimization, so these numbers help with my own personal fears about performance.)
----
I'll test the performance of unsorted arrays soon and post the results here.
How disappointing. Mori[1] (which uses ClojureScript's data structures) was either the same as Immutable-js, or significantly worse. In the end, AVL trees win by a large margin for small to medium dictionaries, while Immutable-js performs better for large (> 100 keys) dictionaries.
Get/insert/remove 1 key:
Immutable AVL Tree x 37,909,434 ops/sec ±0.37% (101 runs sampled)
Immutable-js Map x 19,492,874 ops/sec ±0.15% (101 runs sampled)
Mori Hash Map x 2,306,565 ops/sec ±0.74% (96 runs sampled)
Mori Sorted Map x 13,424,409 ops/sec ±0.51% (97 runs sampled)
Immutable AVL Tree x 6,257,569 ops/sec ±0.43% (99 runs sampled)
Immutable-js Map x 2,111,085 ops/sec ±1.07% (91 runs sampled)
Mori Hash Map x 1,553,193 ops/sec ±0.77% (93 runs sampled)
Mori Sorted Map x 3,785,671 ops/sec ±0.43% (96 runs sampled)
Immutable AVL Tree x 3,426,260 ops/sec ±1.38% (97 runs sampled)
Immutable-js Map x 1,415,893 ops/sec ±0.41% (96 runs sampled)
Mori Hash Map x 699,113 ops/sec ±0.40% (98 runs sampled)
Mori Sorted Map x 1,550,116 ops/sec ±1.54% (100 runs sampled)
Get/insert/remove 10 keys:
Immutable AVL Tree x 21,954,005 ops/sec ±0.81% (98 runs sampled)
Immutable-js Map x 17,236,706 ops/sec ±1.02% (99 runs sampled)
Mori Hash Map x 2,474,120 ops/sec ±0.77% (95 runs sampled)
Mori Sorted Map x 911,264 ops/sec ±0.41% (100 runs sampled)
Immutable AVL Tree x 399,700 ops/sec ±0.15% (97 runs sampled)
Immutable-js Map x 218,274 ops/sec ±0.63% (98 runs sampled)
Mori Hash Map x 150,978 ops/sec ±0.74% (96 runs sampled)
Mori Sorted Map x 73,598 ops/sec ±0.68% (98 runs sampled)
Immutable AVL Tree x 135,120 ops/sec ±0.76% (99 runs sampled)
Immutable-js Map x 100,893 ops/sec ±0.20% (97 runs sampled)
Mori Hash Map x 74,750 ops/sec ±10.95% (96 runs sampled)
Mori Sorted Map x 42,696 ops/sec ±0.45% (99 runs sampled)
Get/insert/remove 100 keys:
Immutable AVL Tree x 6,467,149 ops/sec ±0.38% (93 runs sampled)
Immutable-js Map x 14,233,214 ops/sec ±1.05% (96 runs sampled)
Mori Hash Map x 2,513,928 ops/sec ±1.24% (98 runs sampled)
Mori Sorted Map x 384,132 ops/sec ±0.53% (98 runs sampled)
Immutable AVL Tree x 19,760 ops/sec ±0.52% (100 runs sampled)
Immutable-js Map x 12,798 ops/sec ±0.26% (100 runs sampled)
Mori Hash Map x 10,619 ops/sec ±2.59% (93 runs sampled)
Mori Sorted Map x 3,078 ops/sec ±1.49% (98 runs sampled)
Immutable AVL Tree x 6,420 ops/sec ±0.51% (101 runs sampled)
Immutable-js Map x 6,204 ops/sec ±0.20% (99 runs sampled)
Mori Hash Map x 5,394 ops/sec ±0.81% (93 runs sampled)
Mori Sorted Map x 1,757 ops/sec ±0.51% (100 runs sampled)
So, today I learned that cons cells, despite having O(n) behavior, are really fast. They outperform mutable JS arrays at random inserts!
It's only once you get up to ~100 elements that AVL trees start to outperform cons cells. A good optimization would be to use cons cells for small lists, and then automatically switch to AVL trees once the list grows to be a certain size.
It includes algorithms for getting/inserting/removing an element at a particular index (in the case of arrays), and code for getting/inserting/removing an element in sorted order (for dictionaries and sets).
If anybody wants, I can translate the code from JavaScript to Arc.
---
* [1]: Adding in sorted arrays shouldn't be hard, but I haven't had any need for them yet.
It seems the problem with Anarki is that Arc's lists are terminated with the symbol 'nil rather than Racket's null. So you have to convert from Arc lists to Racket lists (and back again). Here is the relevant code:
In fact, the normal binary search tree deletion can sometimes cause an unbalanced tree when concatting two arrays, but waterhouse's "amerge" function works correctly!
"There are lots of words in the wiki that I don't understand."
Most of the Arc terminology is borrowed from other Lisps, so it's not really a problem with Arc; instead, it's simply that the Lisp culture is very old and has its own way of thinking and doing things. You get used to it.
If you have any questions, please do ask and we'll do our best to answer. Some of us here (including myself) started Arc with almost no Lisp experience, yet over time became quite good.
---
"What are some reusable trail maps that other people have experienced?"
Considering that I'm still learning new things all the time, and that the new things I discover have a tendency to demolish decades-old ways of thinking, I'm not sure there is a nice reusable "just read this and you'll be okay" kind of thing. I do know of at least one good resource for explaining what macros are and why they're awesome, but that's about it. The rest you either have to dig up, ask about, or learn on your own.
---
"How can I learn more about you folk?"
Well, it depends on how much you want to know us. If all you care about is the programming aspect, you can just hang around here and watch what we say and do. You can also ask.
I don't know, that bugs me too. I didn't even know about that link until somebody pointed it out.
---
"Why can't I hover over the language and have it tell me how to refactor my thinking?"
Because good AIs don't exist yet. So it's up to us lowly meat-bags to do the thinking.
---
"How do I ask better questions?"
Everything happens with practice, which takes time and effort. If you really want something and you keep working at it, you'll see improvement. If you don't see improvement, then perhaps your methods are incorrect and you should seek better methods. But keep in mind that some things takes years of hard work, and there may not always be a way to speed it up.
Just focus on improving things bit by bit and after a long period of time, when you look back, you'll see amazing accomplishments. Every journey starts with a single step and all that jazz.
---
"Is there a periodic element of lisp-y things?"
Kinda. Lisps do share some things in common, like S-expressions, macros/vaus, code-is-data-is-code... but the Lisp culture also deeply values individuality and giving programmers more power. So despite some overlap, you tend to see a lot of variance between Lisps, as people try out different things.
---
"Why exactly can't we make improvements again? May I?"
We can't make improvements because pg has been too busy. However, there is a fork of Arc called Anarki, which anybody can change:
"I believe there needs to be a search engine to help me answer that."
If you want to search for something on the Arc Forum, I've found the best way is to go to google.com, and then do this:
site:arclanguage.org foo
---
"Why can't JS just be a Wart?"
Oh man I can go on and on about JS. The answer to your question is pretty long and detailed. If your question is, "why isn't JS better?", well... that's a history lesson that people smarter than me have already gone into:
But things take time. Especially because they have to worry a lot about backwards compatibility.
Also, even though JS is worse than say, Arc, it is possible to write a compiler that takes some dialect of Lisp and compiles it to JavaScript... for an example of that, see my language Nulan:
"They ought to have a gentler guide to show them that. It (might be) automatable, but at first it ought to be distributed. You folk obviously have lots of experiences doing things. Could this guide be possible?"
Are you talking about making a guide about guides, or a guide specifically to help people to understand Lisp? I'm sure either one is possible, but this particular community should have a much easier time with the Lisp guide than the general guide.
That actually sounds like a pretty good idea: a single consolidated guide to help people understand the Lisp way of doing things. Of course we've written plenty of stuff already (as have people not on the Arc forum), but it's scattered everywhere and isn't really coherent. Something like the "learn you a Haskell for great good" but for Lisp sounds nice. Is that what you're talking about?
---
"you can decide immediately(or within ~10min) if someone's cool."
Even if that's true, that isn't necessarily useful. "Coolness" is arbitrary and cultural. It shifts over time. It isn't necessarily tied to quality. And I think that people who seek coolness tend to produce lower quality stuff. After all, any time and energy spent being cool is time and energy spent not improving in non-cool (but useful) ways. Though I myself am guilty of sometimes doing things for the sake of reputation, I try not to do that.
---
"How exactly did you parse it into such a coherent roadmap so quickly?"
I'm just that kinda person: somebody who's quick to read into things. Unless it's rocketnia doing the talking, then I have a much harder time. :P
---
"Must I fork my own version of Arc to do it? Is there a simpler way?"
Yes. And as I mentioned, people have already done so. I personally recommend Arc/Nu, though Anarki should work fine too. Also, since the Arc source code is provided, you can of course modify your local copy as well.
I'm sorry to do this since you edited your post, but here's what your post looked like when I first saw it. I cast a downvote, and I want to clarify why I did that.
"Because I can't tell if `Pauan` is human or not, I'd like to define exactly how `Pauan` arrived at this answer in the community-managed fork of Arc. Is this possible? (yes no)."
If I understand you correctly, you're asking if we could please open-source Pauan (or a subsystem thereof) for the sake of future development and discussion. No. Please don't undermine the voices of people on this forum.
- You're asking an in-depth question about someone in the third person, when they're right here to explain.
- It seems to me you're discriminating on the basis of someone's involuntary implementation details, without any obvious and respectable reason.
- You're suggesting to "define exactly" something which may be an essential secret ingredient in someone's appearance of individuality. As far as I'm concerned, you might as well suggest we zap someone's brain or hound them with paparazzi.
If you're conducting some kind of experiment in the design of cultural conventions, I (for one) don't yet understand and trust you well enough to play along. Would you mind introducing yourself in a more boring way for a while?
It's fine. We're talking in private now, so it shouldn't be a problem anymore.
Also, it's time that I leave the Arc Forum. You all are free to follow my projects on GitHub (https://github.com/Pauan) and can e-mail me at pcxunlimited@gmail.com
Thanks for the apologies. As for me, I wanted to stop you from getting carried away and potentially causing harm to people, but I'm sorry if I've given you a bad experience in the process.
I had seen that blog post of yours. I also particularly noticed this tweet you retweeted, which aptly summarizes a common theme between your blog and your Arc Forum posts:
Founders: What are you doing right now? Is that thing a 10X
improvement or a 10% improvement? Always work on 10X. Every
minute counts.
This kind of mindset can be encouraging, but it seems like it's causing you negative stress. If so, I hope you can set aside some extra time for other things you like to do, even if they feel unproductive. I don't know if those things will be remotely on-topic for Arc Forum, but feel free to bring them up if they are. :)
Yeah I saw those and remember thinking they were nothing like his writings here.
Last night he started email-bombing me and others all sorts of irrelevant statements about google support, venture capital and whatnot. From midnight to 3am yesterday I received 27 emails from him. (I haven't read them all.)
Arc/Nu used to have keyword arguments, but they were a pain in the butt to implement, and only a single function actually used them, so I took them out.
So, it's possible, yes, but not easy. At least, not easy using Racket's keyword arguments. It might be easier if I did everything from scratch...
I specifically designed it so it can run stand-alone, without any dependencies on the rest of Nulan. It takes a string and returns a JS array of strings, numbers, and Symbols. You can easily write a simple function to transform the output so that it's compatible with wat.
You're also free to modify it, though I'm not sure what license to use for Nulan. It'll probably be either the BSD/ISC license or Public Domain.
