6 ms·
The intricacies of implementing memoization in Ruby
- User23 2y agoIt’s fun how the runtime in seconds for the naive Fibonacci is 36: 14930352 (1.2s) 37: 24157817 (2.0s) 38: 39088169 (3.2s) 39: 63245986 (5.2s) 40: 102334155 (8.3s) 41: 165580141 (13.5s) 42: 267914296 (21.8s) What a familiar pattern in those runtimes!
- izietto 2y agoFibonacci never stops surprising!
- JadeNB 2y agoThat's a neat observation! But isn't it for the naïve reason that, with negligible overhead, the run time of executing `fib(n) = fib(n - 1) + fib(n - 2)` is the run time of executing `fib(n - 1)`, plus the run time of executing `fib(n - 2)`? On the other hand, if someone had asked me for an estimate on the run time, I probably would have tried breaking out the master theorem instead of thinking of this, so I don't want to downplay the observation.
- bmm6o 2y agoRight. Also note that the non-optimized implementation boils down to computing F(n) = 1+1+1+1+...+1, with a function call tree that has 2F(n) nodes. So no matter what the relative cost is for addition and function calls, the total time should go like F(n).
- thih9 2y agoI know it’s pointless but now I’d like to see a fibonacci implementation that returns these runtimes as the result.
- kazinator 2y agoAnother kind of fun with Fibonacci (sort of): https://news.ycombinator.com/item?id=14331627 https://news.ycombinator.com/item?id=14331627 floor(x + 0.5) wants to be round(x), that function having been introduced in C99. Just remnants of old school C coding.
- thih9 2y ago> My preferred approach to [thread safety] is to explicitly not think about thread safety, and delegate this concern to the caller. Good call IMO. If I was the author then I’d implement this; it would mostly work for current use cases, would be a pain to maintain and impossible to extend. I learned something today.
- tomchuk 2y agoCan't mention Fibonacci and memoization in the same sentence without me breaking out my favorite Python party trick: def fib(n, cache = {0: 0, 1: 1}): if n not in cache: cache[n] = fib(n-1) + fib(n-2) return cache[n]
- jaggederest 2y agoThe directly translated ruby version (from stack overflow of course) is even shorter: def fib(n, cache=Hash.new{ |h,k| h[k] = k < 2 ? k : h[k-1] + h[k-2] }) cache[n] end It runs out of stack around 7146 on my machine at least. The python one is limited by the recursion depth limit in my test but of course that's configurable at your own risk.
- vidarh 2y agoIf you're first going to golf it, endless-def: def fib(n, cache=Hash.new{ |h,k| h[k] = k < 2 ? k : h[k-1] + h[k-2] }) = cache[n]
- jaggederest 2y agoIt's actually kind of ungolfed. The default version would be just fib = Hash.new{ |h,k| h[k] = k < 2 ? k : h[k-1] + h[k-2] } fib[7145]
- inopinatus 2y agoThis is the proper Ruby form since it relies on the [] operator and is therefore substitutable for any other callable esp. procs/lambdas, and able to wrap them as well. This isn’t just golf, it’s an excellent way to pass around a lazily computed, self-caching closure. I use it often in preference to memoization gems. Aside from noting the false/nil equivalence concern, the original article seems over-engineered to me. Excessive metaprogramming is a common trap for Ruby devs.
- nyrikki 2y agoIMHO, the mamul form is even better for golf, F(n) in O(n log n)
- jmull 2y agoIn real code I've only actually seen memoization used as a cache. That leaves cache validation to some higher level which is in a poor position to do it very well. In my experience, most often it means someone has to figure out what things to manually restart, and when.
- kazinator 2y agoYou mean invalidation? Speaking of invalidation, the memoized Fibonacci will work even with a cache of 1 item that is replaced each time. (By work, I mean slash exponential time to linear.) If you calculate fib(n - 2) first and cache it, evacuating everything else in the process, that is good enough: when f(n - 1) needs f(n - 2), it finds it instead of recursing, and so the multply-and-surrender logic is disrupted, resulting in time proportional to n.
- JadeNB 2y agoWith all that it borrowed from Perl, I'm surprised Ruby didn't also borrow the defined-or operator `//=` (https://perldoc.perl.org/perlop#Logical-Defined-Or https://perldoc.perl.org/perlop#Logical-Defined-Or). (Or, if it did, I guess the author hadn't encountered it.)
- bradly 2y agoI don't think Ruby has this natively, but Rails adds it with Object#presence. https://api.rubyonrails.org/classes/Object.html#method-i-presence https://api.rubyonrails.org/classes/Object.html#method-i-pre...
- tprynn 2y agoActiveSupport adds tons of great convenience methods to Ruby and you can require it even outside of Rails! blank, present; date and time conversions like 1.month.from_now; except; enumerable methods like pluck... It's just lovely require 'active_support/all' https://guides.rubyonrails.org/v5.2/active_support_core_extensions.html https://guides.rubyonrails.org/v5.2/active_support_core_exte...
- JadeNB 2y ago> I don't think Ruby has this natively, but Rails adds it with Object#presence. > https://api.rubyonrails.org/classes/Object.html#method-i-presence https://api.rubyonrails.org/classes/Object.html#method-i-pre... It's not immediately obvious to me how one could use that to write a Ruby analogue of `a //= b`. If I understand correctly, it would still need to be the relatively verbose `a = a.present? ? a : b`. (I think even `a = a.presence || b` wouldn't work in case `a` was defined but nil, which is exactly the edge case the defined-or operator is meant to handle.)
- the_sleaze_ 2y agoI use this to memoize instance vars from time to time, whenever nil could be considered valid return x if defined? x x = ingest_stock_market `defined?` won't evaluate the parameter either which is nice whereas things like blank? present? and presence do
- mmahemoff 2y agoI've come across memoize gems before and thought, "do I really need to introduce a dependency when I can save results into a hash", but this makes a convincing argument to leverage a gem like memo_wise. Clean DSL syntax and the perf gains are much nicer than micromanaging it.
- jacobevelyn 2y agomemo_wise maintainer here. No pressure from me to try it out, but if you do use it and have any feedback or suggestions please let us know!
- nixpulvis 2y agoThere are only 1 hard problems in computer science: memoization and ... shoot what was it again?
- mtkd 2y agoWith any Ruby code under load, it's important to have a proper understanding of what's happening in memory -- if adding memoisation is yielding significant gains, there's likely much more potential for optimisation Many in the Ruby community have taken a 1974 quote from Donald Knuth out of context and used it as a justification for minimal or zero effort on memory efficiency The article is a very interesting read, but implementation is heavily reliant on metaprogramming magic that can be something of a grenade in realworld projects especially if anyone fairly new to Ruby has to fix it later Almost none of the gems I used 10 years ago still exist today -- taking a small penalty for hand-rolling initially will usually save days or more later -- the author even says a similar earlier Gem he built is long gone
- bradly 2y ago> if adding memoization is yielding significant gains, there's likely much more potential for optimization Most often when I see memoization in Ruby code it is when fetching data from either a db or external service. Memory isn't the concern is these cases. > Almost none of the gems I used 10 years ago still exist today -- taking a small penalty for hand-rolling initially will usually save days or more later -- the author even says a similar earlier Gem he built is long gone With a clean DSL changing the gem or removing it for your own solution should not be problem.
- mtkd 2y agoIf app is repeatedly asking DB for same data and it's immutable for a period -- the persistance choice is wrong There is potentially a whole lot of memory/callstack overhead involved in a request like that even when memoised It likely should be in a memory structure all the time or Redis if sufficiently complex / shared across processes etc. as all the other processes will likely be doing same Only in Ruby world would someone say yeah what we need right there is a Gem with some define_method sprinkles
- wutwutwat 2y ago> If app is repeatedly asking DB for same data and it's immutable for a period -- the persistance choice is wrong Says who? ACID databases are the norm for a reason. > There is potentially a whole lot of memory/callstack overhead involved in a request like that even when memoised So because there is overhead elsewhere you shouldn't optimize here? > It likely should be in a memory structure all the time or Redis if sufficiently complex / shared across processes etc. as all the other processes will likely be doing same Redis doesn't help if the issue is the network io. Accessing anything out of process memory will objectively be slower than accessing in process memory. Doesn't matter if the data is coming from pg, redis, or wherever. If its going across the wire, there will be io latency. > Only in Ruby world would someone say yeah what we need right there is a Gem with some define_method sprinkles Ah, I see this is based on a negative view of ruby in particular. Memoization is a common pattern in basically every language, and can net significant performance wins with very little effort (low hanging fruit). Is it a magic bullet? Nope. But it's nice to have in the tool belt when dealing with an app that's falling on its face and every improvment means you get to sleep better at night.
- 15155 2y agoI see no mention of object shape optimization and why and how excessive rose memoization (or just instance variables in general) can be expensive.
- baggy_trough 2y agoIt would be nice if Ruby had a syntax for memoizing a method that would handle the nil/false case and update the shape at init time.
- jez 2y agoIn a similar line, it would be nice if there were a way to predeclare instance variables so that there was a canonical place to put type annotations for instance variables. Ruby type checkers right now all invent their own ways of declaring the types of instance variables. If Ruby supported something like class A def @instance_variable def self.@singleton_class_instance_variable def @@class_variable end as a way to pre-declare the object shape at class load time, it would be an obvious place to also let type checkers declare the types of these instance variables. (Not saying that this specific syntax is ideal, but rather just that having some syntax for declaring instance variables at load time, not method run time, would solve both the "predetermined object shape" and "predetermined ivar types" problems.)
- jez 2y agoFor those curious, this article is a good introduction to the topic: https://railsatscale.com/2023-10-24-memoization-pattern-and-object-shapes/ https://railsatscale.com/2023-10-24-memoization-pattern-and-...
- deleted 2y ago[deleted]
- bwilliams 2y agoGreat article, memoization is pretty complex and full of trade-offs. We recognized a lot of these same pitfalls as we worked through making memoization a consistent and common pattern in our (very large, monolithic Rails) codebase via a `memoize def...` helper. The `false` and `null` pitfall is _surprisingly_ common, enough that it (and other pitfalls) warranted us writing our own memoization DSL. We took the opposite approach of most libraries though (and a reason we rolled our own instead of pulling in an existing gem) by avoiding handling the complex edge cases that hide trade-offs: 1. Class methods can't be memoized. 2. Methods with arguments can't be memoized (so no LRU caches, weak refs, tracking arguments, handling default args, hash/deep object equality, etc) The thought at the time was that those more complex scenarios deserve more thought than "prefix it with `memoize`". It's been a few years since we introduced the helper and after seeing it all throughout our codebase with no issues I'm even more confident this was the correct decision. I haven't revisited it in a while, but I'd love to add some extra niceties to it, like hooking into `ActiveRecord`s `#reload`, although I dislike memoizing in models.
- kazinator 2y agoIn TXR Lisp, I implemented an original invention of mine called Paremeter List Macros (Parameter Macros for short). A parameter macro works in any lambda syntax. Methods, macros. The documentation for Parameter List Macros shows an example implementation of rudimentary memoization. https://www.nongnu.org/txr/txr-manpage.html#N-C9CAE162 https://www.nongnu.org/txr/txr-manpage.html#N-C9CAE162 You can use :memo in a method if you like, in a lambda expression, defmacro, macrolet, labels, ...: anywhere you have a lambda parameter list. There is a predefined parameter macro called :key which implements keyword parameters. (Common-Lisp-like keyword parameters are not native to the language run-time at all: you have to use this param macro if you want them.) Another predefined parameter macro called :match allows you to express a function with pattern matching. :match will take stock of your patterns and implicitly generate a parameter list which can take any of those patterns, and a function body which then further handles the cases.
- jweir 2y agoWe no longer use memoization except for older code. New code has anything that needs to be memoized defined in the initialize method. This solves a lot of problems and Sorbet typing is what encouraged us to go this route. Now there could be a branching problem - one branch will not need to call the expensive thing another would not. In reality I have found this never to be the case in our code base. May be different for your designs.
- revskill 2y agoThere are 2 hard problems in ruby: cache invalidation and magic.