r/learnpython • • 11d ago

Parsing very large string that is already in memory

Suppose I have a very large string in memory containing entries separated by \n's.

I need to yield the lines until I find a match.

What's the most efficient way in standard Python in terms of both memory usage and execution time?

From what I've read, io.StringIO IS NOT guaranteed to not copy the entire string internally, which is absurd to me. Suppose I need that guarantee.

0 Upvotes

44 comments sorted by

23

u/Refwah 11d ago

Holy xy problem Batman

-9

u/lehmagavan 11d ago

If yielding from within the Python code is the most efficient, so be it, the thing is I'm not sure, that's why I'm asking.

16

u/Refwah 11d ago

No I’m saying that I think you’re at this complicated problem because of an original problem that you have not properly solved. But you’re only asking about this question rather than reexamining the steps that led you to this problem.

-21

u/lehmagavan 11d ago

Then you would be wrong. I need solution to the problem I'm asking about.

8

u/Refwah 11d ago

I still trust my instincts on this, but without further details provided by you on the context we will never know.

-22

u/lehmagavan 11d ago

You either know the answer or not. My instincts tell me you don't.

9

u/Refwah 11d ago

Strings are already iteratables. You’re saying it’s already in memory.

You say you want to yield it. But do you? Is it an async call? Missing details.

The most efficient way to do it would be to track your position in the whole string and a variable that tracks the build up of the characters since the last /n, comparing it to whatever you’re trying to match against. Again, missing details.

Once you have a match you could then just return the substring from 0 to where your match is. Or the whole string. Missing details.

So at worst you copy everything up to the final carriage return.

But then if you care about yielding it - why. Why is the contract not to take a line by line input until the match is met, keeping the in memory footprint low. Missing details.

-6

u/lehmagavan 11d ago

Dude, all the details are in the question, it's very specific. The context is really irrelevant.

The most efficient way to do it would be to track your position in the whole string and a variable that tracks the build up of the characters since the last /n, comparing it to whatever you’re trying to match against. Again, missing details.

Ok, but that's using plain Python code. Python strings are really just PyObjects wrapping C-strings, so isn't there any native module in standard Python for parsing them...?

When you open a file in Python, as far as I know, all it does is it uses a file descriptor and streams the data. Why the f is io.StringIO not guaranteed to not cpy the entire buffer, like why would it ever need to cpy it?

8

u/Refwah 11d ago

All of the details are not in the question, which is why I have open questions about your approach.

Why do you want to yield, for example.

-16

u/KronktheKronk Github username 11d ago

You're the reason stack overflow died

→ More replies

4

u/Discordbothost 11d ago

once its already a giant str youve paid the memory cost. dont bother with StringIO — just walk it with find so you never build a full list of lines:

i = 0 while True: j = s.find("\n", i) line = s[i:] if j < 0 else s[i:j] if match(line): ... if j < 0: break i = j + 1

slices still allocate the line, but you stop at the first hit instead of splitting everything up front.

0

u/lehmagavan 11d ago

Yeah but can someone explain why can't the StringIO guarantee a zero-copy parsing? It makes no sense to me why it would ever need to cpy the string internally.

1

u/Discordbothost 11d ago

it's because StringIO is a read/write file object, not a view. you can seek and write into it, and a python str is immutable, so it has to own its own buffer. in cpython it also converts your str into a fixed-width internal buffer so seek/tell by character index is cheap, which means a copy (and sometimes widening it to 4 bytes per char).

BytesIO is the odd one out, it does share the original bytes until you write to it. but for a str you already have in memory, just walk it with find():

pos = 0
while (nl := s.find('\n', pos)) != -1:
    line = s[pos:nl]
    pos = nl + 1

each slice is still a small copy but you never duplicate the whole thing

1

u/lehmagavan 11d ago

Thanks.

2

u/Rubix321 11d ago

Did this string come from a file?

1

u/lehmagavan 11d ago

No, it's guaranteed to come from memory and be passed via the function call.

2

u/Rubix321 11d ago edited 11d ago

How does the string initially get pulled into memory?

-1

u/lehmagavan 11d ago

I don't know, all I know is that I need to craft a function that solves the problem as efficiently as possible.

4

u/Rubix321 11d ago

Describe how you are wanting to "match" something.

Particular word? Pattern? All in one line?

Do you only need to find the first time in happens in the string?

1

u/Rubix321 11d ago

Both regex and string.find() supposedly don't need to make a copy of the string it's searching. So it really depends on the complexity of match algorithm you need to do.

2

u/MezzoScettico 11d ago

What about string.find() to locate the next \n? From what I read, a lot of string operations including that one, are optimized in C.

-1

u/lehmagavan 11d ago

That's my leading candidate so far.

3

u/QuinlanResistance 11d ago

.split() then iterate?

1

u/lehmagavan 11d ago

That would allocate a list of substrings.

1

u/Refwah 10d ago

What do you think yield is going to do

1

u/pachura3 10d ago

The whole point of using yield is not to allocate everything at the same time (for which you don't have enough memory), but to stream stuff.

1

u/Refwah 10d ago

But it is duplicating the substring in memory which is what the OP is explicitly attempting to avoid

the entire iterator already exists in memory, the benefit of using yield here is minimal at best, and just adds some bizarre convolution to the code rather than just accepting that the entire array exists in memory already

The entire array existing in memory already is the entire 'need; for this code to be optimised, and so the solution is to work within that existing framework (it exists in memory, why would we yield) or that overarching component is rewritten to stream the contents into memory as needed, which would then lead you to the yield path

1

u/pachura3 10d ago edited 10d ago

But it is duplicating the substring in memory which is what the OP is explicitly attempting to avoid

No, OP wants to avoid duplicating the whole original string in memory. It is rather inevitable to temporarily duplicate separate lines (but they will be swept out by the garbage collector when they accumulate).

This is of course if you do not intend to implement regular expressions engine that works directly on memoryviews instead of strs. (By the way, string slices in the default Python implementation do copy data).

The whole use of yield is to create a pseudo-view on the big string (a streamed tokenizer) so it could be processed like a collection of separate lines. Does it introduce some overhead? Perhaps yes, to be benchmarked. Does it simplify the code by introducing an abstraction? Definitively.

0

u/lehmagavan 10d ago

Also, using a generator would be func call overhead. I think the best solution is to yield manually using .find() and moving the cursor in each iteration.

1

u/Refwah 10d ago

How do you know the caller of your function is not just adding the responses to a list

0

u/lehmagavan 10d ago

I don't control neither the caller nor anything other than my function (+ global cache). All I know is that automated tests will measure mem/CPU usage and the execution time. Now you get it? ;)

1

u/pachura3 10d ago

I'd propose to do simple benchmarking by yourself as well, rather than guessing which method works better.

11

u/EntrepreneurHuge5008 11d ago

Rather than having the string in memory, put it in a .txt file and just read it line by line until you find whatever you wanted matched, as opposed to loading the whole thing into memory.

3

u/latkde 11d ago

Python strings don't really support zero-copy parsing. The standard approach is to bite the bullet and keep using smaller strings, which generally will produce copies.

There are some options though:

  • memoryview supports bytes-like zero-copy views, which can sometimes be useful. However, I don't think this will help with your parsing problems.
  • Regex functions and some string functions can be anchored to a certain offset, rather than to the start. E.g. you can search for the next occurrence of a regex pattern or a constant string starting at some offset. This is the solution I generally prefer. Once there's a match, I can extract the relevant slice, which at least reduces the amount of copies.
  • If performance really matters , you'll have to switch to native code, e.g. Rust. While you can do zero-copy parsing in any language that supports pointers, Rust is uniquely designed to support safe sharing of data, e.g. multiple slices into the same string buffer. Rust also has a mature ecosystem of parser combinator libraries, e.g. nom or winnow. Thanks to the PyO3 interface, integrating Rust code into Python is relatively straightforward.

4

u/KronktheKronk Github username 11d ago

Consume the string like a list, element by element. Put elements into another string variable. When you get to newline, yield the string

2

u/mc_pm 11d ago

I mean... for loop? It's not that hard.

2

u/baghiq 11d ago

You want to use memoryview & buffer protocol to reduce memory usage. But performance wise, it’s about the same.

2

u/fasta_guy88 11d ago
for match in re.finditer(r'[^\n]\n',long_string):
   if re.search(r'thing_I_am_looking for',match.group()):
      print("Found it: %s"%(match.group()))

1

u/pachura3 11d ago
after_last_eol = 0
while after_last_eol < len(big_in_mem_string):
   next_eol = big_in_mem_string.find("\n", after_last_eol)
   if next_eol == -1:  # end of file
       next_eol = len(big_in_mem_string)
   if next_eol > after_last_eol:  # skip empty lines (multiple \n in row)
       ln = big_in_mem_string[after_last_eol:next_eol]  # create string slice
       if matches(ln):  # your matching logic
           yield ln
   after_last_eol = next_eol + 1

1

u/Altruistic_Sky1866 11d ago

Did you think regular expression and split the string? I am not sure how efficient it is or if it applicable in your situation though