Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Repo info
Activity
  • Jul 26 13:18
    mauricioszabo commented #249
  • Jul 26 07:48
    alexdowad commented #249
  • Jul 24 06:56
    dubek commented #249
  • Jul 22 19:14
    mauricioszabo opened #249
  • May 19 10:31
    dubek commented #248
  • May 16 18:14
    alexdowad opened #248
  • May 16 18:13

    alexdowad on fix_hash_equal

    Hash#== peforms numeric convers… (compare)

  • May 16 18:04
    alexdowad commented #247
  • May 16 18:02
    alexdowad commented #247
  • May 16 18:00
    alexdowad commented #247
  • May 16 17:56
    alexdowad commented #247
  • May 15 21:42
    mauricioszabo opened #247
  • May 05 18:49
    ivoanjo closed #242
  • Apr 01 06:55
    scepticulous closed #223
  • Jan 04 20:55
    alexdowad closed #210
  • Nov 17 2018 19:28
    tdreyno commented #246
  • Nov 17 2018 09:24
    alexdowad commented #246
  • Nov 16 2018 18:49
    alexdowad commented #246
  • Nov 14 2018 21:58
    tdreyno commented #246
  • Nov 14 2018 21:57
    tdreyno commented #246
Alex Dowad
@alexdowad
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
@alexdowad
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
@alexdowad
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
@elben
Great novel :)
Kurtis Rainbolt-Greene
@krainboltgreene
@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
@alexdowad
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
@alexdowad
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
@alexdowad
I found #filter in the README -- just pushed a fix
Thanks for noticing that
Kurtis Rainbolt-Greene
@krainboltgreene
Sweet.
Dov Murik
@dubek
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
@krainboltgreene
@dubek: Got nothing, a lot of the original code was "in transition" or experimentation.
Alex Dowad
@alexdowad
@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
@alexdowad
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
@dubek
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
@alexdowad
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
@krainboltgreene
Ha, it works.
Dov Murik
@dubek
Hey @krainboltgreene , thanks for releasing gem v2.0.0. When I look in the releases page https://github.com/hamstergem/hamster/releases 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
@krainboltgreene
Bleh, not really. They are pretty bad about versions. I'll bring it up with Rubygems.
Thanks for letting me know @dubek
Dov Murik
@dubek
@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
@krainboltgreene
Ohhh
Hmm.