v8 Caching Behavior

[eliotwrobson]

Followup discussion from this thread: #147 (comment)

@EduardoGoulart1 What are your thoughts on having an enum with the cache levels given in this discussion?

Re: the paper you linked, that's the algorithm I was referring to. That algorithm has complexity depending on the number of transitions, so for a partial DFA over a large alphabet, that algorithm should be substantially faster.

[eliotwrobson]

Related: for some of the word caching and computation, it may help to replace some of the lists with arrays (https://docs.python.org/3/library/array.html) to alleviate the memory issues (along with being faster).

[eliotwrobson]

Looking at this again, I think it might actually be better just to add a function that allows for manually clearing the caches on DFAs. I'm not opposed to having a global enum control this, but manual clearing seems like a more practical solution.

What are your thoughts @EduardoGoulart1 ?

[caleb531]

@eliotwrobson @EduardoGoulart1 In my opinion, I'm not sure a function to clear the cache will entirely solve the problem (that a global config setting would otherwise address). What if the language space is so large and memory is inflated before you can clear the cache?

In other words, a function to manually clear the cache is not a preventative solution; the purpose of a configurable option is to prevent the cache from growing excessively.

[eliotwrobson]

@caleb531 saying that the words computed belonging to a DFA are "cached" is a bit of a misnomer; the algorithm used to compute these words builds them up in a bottom-up manner using those computed in the previous iteration. Essentially, the algorithm itself used here has inherently high memory usage. There is a trick to somewhat improve the memory usage (dynamically clearing previous levels as all of the corresponding words are read), but the current level being read has the highest potential memory usage anyway (as it has the most words of the longest length). So even adding a global config, the best we can really do is clear out the stored results from this algorithm after it's done executing (which may be tricky the way that iterators are set up). However, I would definitely be in favor of optimizations that involve choosing more efficient data structures.

I'm still skeptical that this is a significant issue because of the following:

1. The successors function also generates all of the words belonging to a DFA (with additional fine-grained controls) using a more memory-efficient algorithm (wall following). If a user is concerned about memory usage, they can just stick to using this function and avoid the default iteration altogether. Although a bit orthogonal to the main point here, I think we shouldn't change the current default algorithm, as this is the faster of the two algorithms (I believe successors is slower because of time taken to build up each word, but it may be worth benchmarking).
2. Generally, memory efficiency isn't as much of a concern on modern hardware (this is the reason that much more research is devoted to optimizing time complexity rather than memory complexity of algorithms). In particular, I've made a DFA corresponding to an entire English dictionary and then read off the contents, and didn't run into any memory-related issues. I know that Python is notorious for inefficient memory usage, but I'm still not sure that this is something that's going to be a huge issue in the wild (especially given 1).

With respect to this library, I'm generally much more concerned about speed issues (as this is written in pure Python and
some previous implementations of the algorithms had usability problems because of the speed), and am willing to sacrifice some memory efficiency under the hood in service of speed, as people are far more likely to run into these issues than running out of memory.

In summary, I'm not strongly opposed to adding more options in caching behavior (especially if these are opt-in features), but I think this is really overkill for something that isn't affecting many people. However, I haven't run any memory profiling myself, and I am definitely open minded if there is memory profiling showing that people are running into problems.

(Sorry this turned into a huge essay, I tried to be too comprehensive and got carried away 😅 )

[caleb531]

@eliotwrobson Those are all good points—thanks for laying those out. You have convinced me that a clear-cache method would be a sufficient solution for this.

But just to be clear, you're thinking of a public method (as opposed to a static/class method) that would only clear the cache for a single DFA per call, correct?

[eliotwrobson]

@caleb531 yes, that's what I had in mind. Just a public method that lets client code empty the word and count caches for a DFA instance.

Along with this change, we can take a look if other things can be cached as well (like whether or not a DFA is empty, for example).

[caleb531]

@eliotwrobson Yep, both of those ideas sound great to me. And the best part is: a clear_cache sort of method can peacefully coexist with any caching level-based configuration we might decide to add in the future. That is, these solutions are not mutually-exclusive.

So with that, I'd say you're welcome to go ahead and implement something + submit a PR if you have the time to do so.

cc @EduardoGoulart1

[eliotwrobson]

Going to go ahead and close as #152 has been merged, where additional caching and cache clearing options have been implemented.

[EduardoGoulart1]

First about the usage of arrays: I would not do it... I have little experience with them, but I think that the library being pure Python is a strong selling point as it's much easier to debug and work with. If the user wants the best performance, then they should go for something like openFST or MONA

The library has two caches: the word_length cache and the word_cache. The first is relatively small and I can't imagine a situation where this would cause problems. The second grows exponentially with the maximum length of words cached and it's only used to iterate over the words of the language in alphabetical order. Yes, I agree that memory is often not the bottleneck for modern applications, especially considering that the library is written in pure Python. However:

• The library wouldn't be able to compute words_of_length(k) for large ks (or even if that would be possible, one would still pay the price to generate all the words of length <k)
• If the user wants to keep reusing words of a certain length, then he/she should be caching it (this is a pretty straightforward optimization that shouldn't add too much complexity for the user)
• The library is silently using memory. It is counter-intuitive that iterating over the set of words of a DFA bloats memory, even after the method is done (this is not what one would expect from iterators in Python)

So for that reason, I would vote for getting rid of the word_cache and implementing it based on iterators (that would need some investigation. I wouldn't be able to tell if that's possible).