Where communities thrive

  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
Repo info
  • Apr 12 08:57
    alexdowad synchronize #250
  • Apr 12 08:55

    alexdowad on fixup_vector_transpose_error

    Vector#transpose raises TypeErr… (compare)

  • Apr 12 08:50
    alexdowad opened #250
  • Apr 11 14:21
    alexdowad closed #196
  • Apr 11 14:15
    alexdowad closed #246
  • Jul 26 2019 13:18
    mauricioszabo commented #249
  • Jul 26 2019 07:48
    alexdowad commented #249
  • Jul 24 2019 06:56
    dubek commented #249
  • Jul 22 2019 19:14
    mauricioszabo opened #249
  • May 19 2019 10:31
    dubek commented #248
  • May 16 2019 18:14
    alexdowad opened #248
  • May 16 2019 18:13

    alexdowad on fix_hash_equal

    Hash#== peforms numeric convers… (compare)

  • May 16 2019 18:04
    alexdowad commented #247
  • May 16 2019 18:02
    alexdowad commented #247
  • May 16 2019 18:00
    alexdowad commented #247
  • May 16 2019 17:56
    alexdowad commented #247
  • May 15 2019 21:42
    mauricioszabo opened #247
  • May 05 2019 18:49
    ivoanjo closed #242
  • Apr 01 2019 06:55
    scepticulous closed #223
  • Jan 04 2019 20:55
    alexdowad closed #210
Alex Dowad
so it will use the same 5 bits to recurse down another level, to a leaf node
then extract the next 5 bits up from the LSB
if the key you are looking for is in the trie, MOST of the time you will find it in a leaf
the number of K/V pairs held in the branches is so limited, statistically, you are unlikely to find the key you are looking for in a branch
so most of the time, those calls to #eql? are wasted
Maybe a few % of the time,
you find the key you are looking for in a branch,
and can avoid recursing all the way down to the bottom of the trie
If you are really interested in the algorithm, instrumenting Trie with some counters could be interesting
To see how many levels (on average) retrieval/insertion/deletion has to recurse down
How many comparisons are done, etc
Alex Dowad
One "interesting" idea: make Trie inherit from Array, so the Trie nodes are actually Arrays, and store state in array slots rather than instance variables
No idea if it would help performance or not. Internally, the Ruby interpreter special-cases Arrays (as well as integers, Floats, Symbols, etc) like crazy
So some operations are faster on Arrays than on other objects in general (even more true for Integers, Floats, Symbols)
On the other hand, setting/retrieving instance variable values is surprisingly fast in Ruby, given that inst variables are all created dynamically
Since I am writing a novel here, let me mention I once tried implementing Trie in C, using something closer to Clojure's tries
Alex Dowad
Retrieval was wickedly fast. But I was very disappointed with insertion/deletion performance
I only ever got it to within a 10x factor of Ruby's Hashes
After very detailed analysis, I concluded that the only way to squeeze closer to insertion/deletion perf of a mutable Hash
would be to write my own garbage collector, optimized for Hamster's use
I don't know how close that would get it. "Modifying" immutable structures, with the associated copying, is inherently not CPU cache-friendly.
Anyways, I'm not crazy enough to dive in that deep. Performance is already good enough for most use cases.
(End of novel) :-)
Elben Shira
Great novel :)
Kurtis Rainbolt-Greene
@alexdowad: Hey, the documentation details Hamster::List#filter, but we don't have that method anymore. I'm guessing it's #take_while?
Alex Dowad
Hi @krainboltgreene
That was removed in 3917c76
I changed filter/remove to use the same names as the Ruby standard library: select/reject
Looks like my commit log comment lost a sentence
Alex Dowad
Probably because I used the Ruby # notation for an instance method name right at the beginning of a sentence, and git took it as a comment
Alex Dowad
I found #filter in the README -- just pushed a fix
Thanks for noticing that
Kurtis Rainbolt-Greene
Dov Murik
Can someone explain in Hamster::List (actually in LazyList) - why do have QUEUE and MUTEX (= global, singletons) and not @mutex and @queue per LazyList instance?
Kurtis Rainbolt-Greene
@dubek: Got nothing, a lot of the original code was "in transition" or experimentation.
Alex Dowad
@dubek: to reduce the memory footprint of each list node.
Lists can be big in some cases. If a list has a million elements, and each one has its own condition queue and mutex to protect the condition queue, that's 2 million extra object allocations.
Alex Dowad
In many cases, lists will only be used from a single thread. On other cases, there may be more than one thread, but access to the list may be uncontended.
If you have more than one list being realized at the same time, and there is contention for both of them, then you will have spurious wakeups. But I haven't seen that to be a major issue for performance.
If you discover that it is actually an issue, please share test results.
Dov Murik
OK got it. Also - a List is just a head and another List, right? So a list with 5 elements basically has 5 List objects in memory (and one EmptyList (which is shared) as the tail of the last one).
Alex Dowad
Yes. That's right. Though the list code is polymorphic, and you can easily add a new list class which will interoperate with the other ones. It just has to define a couple methods.
Kurtis Rainbolt-Greene
Ha, it works.
Dov Murik
Hey @krainboltgreene , thanks for releasing gem v2.0.0. When I look in the releases page I see a v1.0.0 at the top, and below it v2.0.0. Also the v1.0.0 is marked as draft. Any idea how this thing works?
Kurtis Rainbolt-Greene
Bleh, not really. They are pretty bad about versions. I'll bring it up with Rubygems.
Thanks for letting me know @dubek
Dov Murik
@krainboltgreene It's not in rubygems - it's in github. In rubygems hamster 2.0.0 is on top which is cool.
Kurtis Rainbolt-Greene