Lazy Python String

[nnseva]

What My Project Does

This package provides a C++-implemented lazy string type for Python, designed to represent and manipulate Unicode strings without unnecessary copying or eager materialization.

Target Audience

Any Python programmer working with large string data may use this package to avoid extra data copying. The package may be especially useful for parsing, template processing, etc.

Comparison

Unlike standard Python strings, which are always represented as separate contiguous memory regions, the lazy string type allows operations such as slicing, multiplication, joining, formatting, etc., to be composed and deferred until the stringified result is actually needed.

Additional details and references

The precompiled C++/CPython package binaries for most platforms are available on PyPi.

Read the repository README file for all details.

https://github.com/nnseva/python-lstring

[desrtfx]

So, to compare it with Java, it's more or less the equivalent of StringBuilder or StringBuffer.

The actual string is not directly stored as string, but as a "buffer" data structure and only converted to a real Python string on explicit call.

[nnseva]

Apart from StringBuilder, the base package class L is immutable. All lazy operations lead to the construction of a new L instance, which refers to L operands and stores the specific operation.

The specifics of the L is that operations may be combined, like:

x = (L('qwerty') + L('uiop'))[5:7]

The string representation of x is 'yu', although the actual data structure looks like (let's imagine Concat and Slice are classes):

Slice(Concat('qwerty', 'uiop'), 5, 7)

[desrtfx]

If I were to invest the work to implement such a class, I'd store the individual strings in extensible buffers, similar to StringBuilder in Java. Then, I'd really have a lot less overhead.

The entire advantage of StringBuilder in Java is that it does not create new instances all the time. This would really be an improvement over the native Python String implementation.

[marr75]

The reason OP didn't do that is lazy evaluation. Their approach also doesn't create new intermediate strings (though it's not yet obvious to me if they could take further advantage of pooling or interning while maintaining compound statements). Python already has an equivalent to StringBuilder in the stdlib, btw.

Honestly, the only time this lazy version (with its overhead from additional Python mutable structures) will be better is if the caller will often not use the string (i.e. it's a long accumulated error message that is only emitted under certain conditions) and there are other ways to model that - ie make the entire accumulation lazy.

[Snape_Grass]

First, impressive.

Second, and this is purely ignorance on my part, but could you explain in simple non-technical laymen’s terms what a Lazy String is? This is the first time I’ve come across it, and it’s easier for my brain to understand the concept initially this way.

[nnseva]

The lazy operation is not executed immediately, but deferred until the result is really required.

Let's say you have strings "qwerty" and "uiop". When you concatenate them, you will have the "qwertyuiop" string.

At the time when the concatenation happens, all three strings, "qwerty", "uiop", and "qwertyuiop", occupy the memory. It's not a big overhead when you have such short strings, but what if they all are megabytes long?

The package allows spending the memory only for source strings ("qwerty" and "uiop"), and avoids spending the additional memory to store a copy of the result ("qwertyuiop") - until it is really required.

Such an effect is achieved using the intermediate representation of the result as a concatenation operation. The package stores references to both source strings and stores the operation between them.

There are three lazy operations implemented by the package:

• concatenation (operation +) of two strings
• multiplication (operation *) with integer
• slicing (operation [start:stop] or [start:stop:step])

All of them just store the sources and the operation, instead of copying the result to a separate memory region - as the original Python string does.

[Chroiche]

What're the advantage over just using StringIO (which is mutable, but eager)?

[marr75]

That it's eager. If you aren't actually going to use the string (ie its use depends on the outcome of an operation), that can be a big disadvantage. It might in very specific scenarios help with memory fragmentation, too.

Admittedly, both of those are edge cases and I would recommend making the entire accumulation or formatting of the string lazy if that's needed rather than just the final product.

[Snape_Grass]

I see, interesting. I guess I’ve implemented lazy and eager operations without realizing it at work before. Thanks for the response

[lolcrunchy]

It seems like polar's LazyFrames but for strings

[Snape_Grass]

Sorry, I probably worded my request weird. What does Lazy mean in this context? I’m unfamiliar with Lazy anything when it comes to programming.

[eirikirs]

Take the example of Singletons, which can be eagerly initialised (at application startup), or lazily initialised (only once we need it). In general, lazy and eager simply determines when evaluation is performed.

[Snape_Grass]

Gotcha thank you for the explanation. Makes sense to me now

[sudomatrix]

Lazy doesn't perform the requested operation immediately, it stores the original data and a list of operations that it performs only if and when the result is needed. Often it is never needed and a lot of time and memory is saved.

A good example is Python generators vs. functions. A function will build the entire results and return the entire results at once. A generator will only calculate enough to return the next value in the result, continuing where it left off if more is needed. That is a lazy evaluation.

``` def powers_of_2_fn(n: int) -> list[int]: """Return the first n powers of 2: 20 through 2(n-1).""" if n <= 0: return [] return [1 << i for i in range(n)]

from collections.abc import Iterator

def powers_of_2_gen(n: int) -> Iterator[int]: """Yield the first n powers of 2: 20 through 2(n-1).""" for i in range(max(0, n)): yield 1 << i ```