Streaming Data Memory Growth

[ELind77]

I have been using spacy for streaming data (twitter and news stories mostly) and I believe that the fundamental design of the vocab/StringStore in spacy is problematic for streaming processing. When used for batch jobs the additional memory overhead of storing a new lexeme struct for each new word form encountered in parsing is negligible compared to the speed gains, and because most text conforms to the assumption that vocabulary size grows logarithmically as the total number of tokens grows linearly this is usually a safe bet. But for streaming text, especially for social media where new terms are invented by the minute (hashtags and URLs in particular) this assumption no longer holds and the spacy vocabulary storage represents a dynamic element in what should be a completely static production deployment.

In order to test this assumption, I took one million tweets and performed a rudimentary analysis using the resources module in python to get the maximum memory used by the program at regular intervals during processing. I first performed some minor preprocessing to remove newlines from the data so that it could be read line by line so that it wouldn't all be kept in memory, then I ran spacy with all models set to false, only the tokenizer loaded. I then did the same thing again after removing all URLs, hashtags, and twitter mentions from the data , and then filtering all empty strings (this resulted in a 1.4% data loss in terms of total tweets processed but that's fairly minor).

The final result was that spacy used an additional 278.6 MB after tokenizing the raw tweets and 60.99 MB of additional memory when tokenizing the pre-processed tweets. This result confirms my hypothesis but also shows that the memory increase really isn't all that significant (especially at the relatively low volume that I am currently processing). But it still points to a potential flaw in the design of the library.

My suggestion/request in the near term would be to have an option to make the vocabulary read only so that users who want to be able to leave spacy alone to do streaming data processing don't need to worry about changing memory requirements. In the long term, I think that an optimal solution would be to add some functionality for a timeout on vocabulary entries that aren't loaded at initialization. E.g. if this lexeme hasn't been accessed for the last n seconds, delete it from the StringStore. And n would be user configurable.

My code and results are available here: https://github.com/ELind77/spacy_memory_growth

Thanks again for continuing to develop such a great library!

-- Eric

[honnibal]

I really need to fix this issue. Thanks.

[syllog1sm]

I think this patch from a few weeks ago might have fixed this. Unfortunately the patch wasn't pushed to master --- I've only just merged it now.

The fix is: 141639e

Could you test this by pip install https://github.com/spacy-io/spaCy/archive/master.zip ?

[ELind77]

Sorry this has taken a while. I'll test again today/tomorrow and get back to you.

[ELind77]

I performed the same tests again, both installing from the zip you posted above and installing directly from master (commit 9cd21ad) and got nearly identical results to my previous trials.

If you believe that this is the cause of some kind of memory leak, I think we should really take a look at my testing script and update it as it's very rudimentary and I'm far from an expert profiler. However, I don't think that this is a leak. As I said in my original post, I think that this is just part of how spacy works. When parsing things like social media where there are many tokens that occur only once (e.g. links) storing them in the StringStore causes memory bloat. In your comments on #172 you proposed a batch-processing generator that uses, and then throws away a tokenizer object for each batch in order to help find OOV tokens. I think that's a fine approach, and could even be done a bit more quickly by asynchronously loading the new English() instance and replacing the old one when the new is ready, but that still leads to quite the slow down.

If your feeling is that spacy is really meant for batch processing and that I should use mini-batches if I want to approximate streaming, I can do that. Spacy is still far superior to anything else out there in my opinion, but it would be nice if I could use it with the expectation of roughly constant space complexity.

-- Eric

[honnibal]

To clarify a little bit, the current release version has three known places that could be growing in memory use.

1. The StringStore
2. A cache in the Tokenizer
3. The Vocab, for tokens that are part of prefix, infix and suffix patterns.

The patch I asked you to try out addresses 3. We can also easily address 2. Addressing 1 is hard, because we currently intern all the strings, which is a much easier policy to implement than something more subtle.

Can you report the lengths of the StringStore class in your two benchmark cases? There's currently no Python API for inspecting the size of the tokenizer's cache, so it's easiest to do this by elimination.

[ptully]

Hi @honnibal, why do you think addressing 1 is so hard? What about FIFO queue or similar, or something like @ELind77 suggested like:

functionality for a timeout on vocabulary entries that aren't loaded at initialization

Do you have any more information on this issue since it cropped up a few months ago? I notice the same type of memory issues on my systems that analyze streaming Twitter data - note I've not yet narrowed it down to spacy yet but my first cursory look found this ticket to be the most relevant possibility

[ptully]

Also curious if this issue is already solved already, I will test updating my version (currently 0.100.6) to see if that helps at all

[natb1]

Hi @honnibal, I have had similar issues in my streaming application. Basically memory grows at a logarithmic-ish pace. We have to deal with it as though it were a memory leak and periodically re-initialize the code.

I ran the benchmark you requested above - collecting metrics on the length of the StringStore as memory usage grows. Here are the results:

Here is the code I used to create the metrics. It basically ran until I ran out of memory on a 4G box. https://github.com/natb1/spaCy/blob/memory-benchmark/spacy/tests/benchmark/test_memory.py

I'd be glad to help implement some strategies to address this problem if you could help me isolate the issue and/or suggest some approaches.

[tomtung]

Same problem here. Would also be glad to help.

[ptully]

pinging @henningpeters given recent announcement on spaCy homepage

[honnibal]

To clarify the current behaviour a little: StringStore is currently interning all strings seen. I agree that this should be changed. I'll discuss the design decision here, so that we can consider the trade-offs.

I'll start from the beginning: why intern the strings? Two main reasons:

1. String-to-int mapping

2. Save memory to represent lots of documents at once.

We can't do without 1 entirely — it's too fundamental to how spaCy is working, and we definitely don't want to be making lots of string comparisons. Comparing by integer value is pretty important.

Consideration 2 is very useful, but it's only really a saving if strings occur multiple times. Certainly, for strings that occur once, there's no advantage. And it's also bad to have unbounded memory use on the streaming process.

So the solution we want to get to is one where a limited number of somewhat common strings are interned in the common vocab. However, we still need to map all strings, even rare ones, to integers. We also want the string-to-int table to be consistent, even for rare strings.

Here's the bit of code where the memory growth is occuring:

https://github.com/spacy-io/spaCy/blob/master/spacy/strings.pyx#L147

The purpose here is to resolve a string to an integer. We first hash the string. Now, this is an integer representation --- so why not just use the hash? The problem is we also want the inverse mapping. We therefore store the string, causing the memory growth.

If we insist that all integers can always be mapped back to strings, there's no solution. We have to accept the memory growth. But if we can accept that these strings pass out of date, so that they're around for a while and then they're not, the situation should be manageable.

A simple way to achieve this is to extend the StringStore so that the mapping is split in two. There's the main intern area, which holds a fixed number of strings, hopefully the common ones. But there's also a rolling buffer, in which strings are interned, and then later freed. This could be a LRU cache, or even something simpler. Efficiency is not really a problem here: only a small percentage of the encountered tokens will be triggering this logic, so we don't have to make it blazing fast, and it's easy to make sure we operate on contiguous buffers.

A slightly more tricky solution is to do some reference counting. The idea here would be for the Doc object to register interest in all OOV strings it owns. When the ref count of an OOV string drops to 0, it's freed. This way, if you keep a Doc object in memory, you know that the string lookup will always be well behaved — but if you're letting the Doc objects pass out of scope, your memory won't be growing.

I think for both solutions, we should use the hash of the string as the integer representation for OOV strings. This means that at least the string-to-int mapping will stay consistent, even if strings are passing out of memory. The only way to have a problem here is if you hold onto the integer representation, release all of the documents, and later want to recover the string. In this situation, you'll be out of luck --- but we'll at least know to use an OOV symbol when you try to look up your string.

[tomtung]

Simply hashing oov tokens sounds good enough to me. As long as we know the
indices of the fist and last characters of the token in the input text, so
that we can look it up if we need to, I don't find saving the token in
string store particularly necessary.

On Thu, Aug 25, 2016, 8:03 AM Matthew Honnibal notifications@github.com
wrote:

To clarify the current behaviour a little: StringStore is currently
interning all strings seen. I agree that this should be changed. I'll
discuss the design decision here, so that we can consider the trade-offs.

I'll start from the beginning: why intern the strings? Two main reasons:

1. String-to-int mapping

2. Save memory to represent lots of documents at once.

We can't do without 1 entirely — it's too fundamental to how spaCy is
working, and we definitely don't want to be making lots of string
comparisons. Comparing by integer value is pretty important.

Consideration 2 is very useful, but it's only really a saving if strings
occur multiple times. Certainly, for strings that occur once, there's no
advantage. And it's also bad to have unbounded memory use on the streaming
process.

So the solution we want to get to is one where a limited number of
somewhat common strings are interned in the common vocab. However, we still
need to map all strings, even rare ones, to integers. We also want the
string-to-int table to be consistent, even for rare strings.

Here's the bit of code where the memory growth is occuring:

https://github.com/spacy-io/spaCy/blob/master/spacy/strings.pyx#L147

The purpose here is to resolve a string to an integer. We first hash the
string. Now, this is an integer representation --- so why not just use the
hash? The problem is we also want the inverse mapping. We therefore store
the string, causing the memory growth.

If we insist that all integers can always be mapped back to strings,
there's no solution. We have to accept the memory growth. But if we can
accept that these strings pass out of date, so that they're around for a
while and then they're not, the situation should be manageable.

A simple way to achieve this is to extend the StringStore so that the
mapping is split in two. There's the main intern area, which holds a fixed
number of strings, hopefully the common ones. But there's also a rolling
buffer, in which strings are interned, and then later freed. This could be
a LRU cache, or even something simpler. Efficiency is not really a problem
here: only a small percentage of the encountered tokens will be triggering
this logic, so we don't have to make it blazing fast, and it's easy to make
sure we operate on contiguous buffers.

A slightly more tricky solution is to do some reference counting. The idea
here would be for the Doc object to register interest in all OOV strings
it owns. When the ref count of an OOV string drops to 0, it's freed. This
way, if you keep a Doc object in memory, you know that the string lookup
will always be well behaved — but if you're letting the Doc objects pass
out of scope, your memory won't be growing.

I think for both solutions, we should use the hash of the string as the
integer representation for OOV strings. This means that at least the
string-to-int mapping will stay consistent, even if strings are passing out
of memory. The only way to have a problem here is if you hold onto the
integer representation, release all of the documents, and later want to
recover the string. In this situation, you'll be out of luck --- but we'll
at least know to use an OOV symbol when you try to look up your string.

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
#285 (comment), or mute
the thread
https://github.com/notifications/unsubscribe-auth/AAfUutsOJ17JS8IRWp2pZNtc6BmNbExsks5qja6tgaJpZM4Ht9oH
.

[honnibal]

The input text is currently not saved/represented on the document at the moment. Instead, we guarantee that the orth attribute faithfully retains the slice for each token, so that we just have to join the orth attributes and check whether the token has a trailing space.

[tomtung]

Yeah I understand. The point I was making was that, since the caller of the Language object has the full input text string anyways, it shouldn't be a big problem to deal with the slight inconvenience of having to look up the original substring of OOV tokens.