Menu
For a project I'm working on, there are a number of states where calculations can be relied upon to return the same results (and have no side effects). The obvious solution would be to use memoization for all the costly functions.
I would need to have memoization that handles more than one state (so that I could invalidate one cache set without invalidating another). Does anybody know a good C library for this sort of thing? (Note that it can't be C++, we're talking C.)
I've worked with some good implementations in Python that use decorators to be able to flexibly memoize a bunch of different functions. I'm kind of wondering is there's a generic library that could do similar things with C (though probably with explicit function wrapping rather than convenient syntax). I just think it would be silly to have to add caching to each function individually when it's a common enough issue there must be some off-the-shelf solutions for it.
The characteristics I would look for are the following:
Anybody know a C implementation that can handle all or most of these requisites?
611
In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
JavaScript Memoization Example The Fibonacci sequence is a set of numbers that starts with a one or a zero, followed by a one, and proceeds based on the rule that each number (called a Fibonacci number) is equal to the sum of the preceding two numbers. It looks like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
Is memoization same as caching? Yes, kind of. Memoization is actually a specific type of caching. While caching can refer in general to any storing technique (like HTTP caching) for future use, memoizing specifically involves caching the return values of a function .
slowdown in initial execution. space overhead. extra burdens on programmers, because it may require programmers to modify code.
Okay, seeing as there were no memoization libraries for C and I was looking for a drop-in solution for memoizing existing C functions in a code base, I made my own little memoization library that I'm releasing under the APL 2.0. Hopefully people will find this useful and it won't crash and burn on other compilers. If it does have issues, message me here and I'll look into it whenever I have the time (which would probably be measured in increments of months).
This library is not built for speed, but it works and has been tested to make sure it is fairly straightforward to use and doesn't display any memory leaks in my testing. Fundamentally, this lets me add memoization to functions similar to the decorator pattern that I'm used to in Python.
The library is currently on SourceForge as the C-Memo Library. It comes with a little user manual and a couple of 3rd party permissively licensed libraries for generic hashing. If the location changes, I'll try to update this link. I found this helpful in working on my project, hopefully others will find it useful for their projects.
103
memoization is all but built into the haskell language. You can call this functionality from c
Update:
I'm still learning about functional programming, but I do know that memoization is fairly common in functional programming becuase the language features make it easy. I'm learning f#. I don't know haskell, but it is the only functional language I know of that will interact with c. You might be able to find another functional programming language that interfaces with c in a more suitable fashion than what haskell provides.
39
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
