New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
The Unicode "lazy strings" patches #44420
Comments
These are patches to add lazy processing to Unicode strings for Python 3000. I plan to post separate patches for both "lazy concatenation" and "lazy slices", as I suspect "lazy concatenation" has a much higher chance of being accepted. There is a long discussion about "lazy concatenation" here: Note that, unlike the 8-bit-character strings patches, I don't expect the "lazy slices" patch to be dependent on the "lazy concatenation" patch. Unicode objects are stored differently, and already use a pointer to a separately-allocated buffer. This was the big (and mildly controversial) change made by the 8-bit-character "lazy concatenation" patch, and "lazy slices" needed it too. Since Unicode objects already look like that, the Unicode lazy patches should be independent. |
What are the performance characteristics of each operation? I presume that a + b for unicode strings a and b is O(1) time (if I understand your implementation correctly). But according to my reading, (a + b + c + ...)[i] is O(number of concatenations performed). Is this correct? |
While I don't think the added complexity in the implementation is worth it, given that there are other ways of achieving the same kind of performance (e.g. list of Unicode strings), some comments:
|
jcarlson: If you're referring to GvR's statement "I mention performance because s[i] should remain an O(1) operation.", here: lemberg: As for causing memory errors, the only problem I see is not checking for a NULL return from PyMem_NEW() in PyUnicode_AsUnicode(). But that's a bug, not a flaw in my approach, and I'll fix that bug today. I don't see how "[my] approach can cause memory errors" in any sort of larger sense. |
Revised the lazy concatenation patch to add (doh!) a check for when PyMem_NEW() fails in PyUnicode_AsUnicode(). |
From what I understand, the point of the lazy strings patch is to make certain operations faster. What operations? Generally speaking, looped concatenation (x += y), and other looping operations that have traditionally been slow; O(n^2). While this error is still common among new users of Python, generally users only get bit once. They ask about it on python-list and are told: z = []; z.append(y); x = ''.join(z) . Then again, the only place where I've seen the iterative building up of *text* is really in document reformatting (like textwrap). Basically all other use-cases (that I have seen) generally involve the manipulation of binary data. Larry, out of curiosity, have you found code out there that currently loops and concatenates unicode? |
Much of what I do in Python is text processing. My largest Python project to date was an IDL which spewed out loads of text; I've also written an HTML formatter or two. I seem to do an awful lot of string concatenation in Python, and I'd like it to be fast. I'm not alone in this, as there have been several patches to Python in recent years to speed up string concatenation. Perhaps you aren't familiar with my original justification for the patch. I've always hated the "".join() idiom for string concatenation, as it violates the "There should be one--and preferably only one--obvious way to do it" principle (and arguably others). With lazy concatenation, the obvious way (using +) becomes competitive with "".join(), thus dispensing with the need for this inobvious and distracting idiom. For a more thorough dissection of the (original) patch, including its implementation and lots of discussion from other people, please see the original thread on c.l.p: And, no, I haven't seen a lot of code manipulating Unicode strings yet, but then I'm not a Python shaker-and-mover. Obviously I expect to see a whole lot more when Py3k is adopted. |
Larry, I probably wasn't clear enough: PyUnicode_AS_UNICODE() returns a pointer to the underlying Py_UNICODE buffer. No API using this macro checks for a NULL return value of the macro since a Unicode object is guaranteed to have a non-NULL Py_UNICODE buffer. As a result, a memory caused during the concatenation process cannot be passed back up the call stack. The NULL return value would result in a plain segfault in the calling API. Regarding the tradeoff and trying such an approach: I've done such tests myself (not with Unicode but with 8-bit strings) and it didn't pay off. The memory consumption outweighs the performance you gain by using the 'x += y' approach. The ''.join(list) approach also doesn't really help if you're after performance (for much the same reasons). In mxTextTools I used slice integers pointing into the original parsed string to work around these problems, which works great and avoids creating short strings altogether (so you gain speed and memory). A patch I would find a lot more useful is one to create a Unicode alternative to cStringIO - for strings, this is by far the most performant way of creating a larger string from lots of small pieces. To complement this, a smart slice type might also be an attractive target; one that breaks up a larger string into slices and provides operations on these, including joining them to form a new string. I'm not convinced that murking with the underlying object type and doing "subtyping" on-the-fly is a clean design. |
lemburg: You're right, the possibility of PyUnicode_AS_UNICODE() returning NULL is new behavior, and this could conceivably result in crashes. To be clear: NULL return values will only happen when allocation of the final "str" buffer fails during lazy rendering. This will only happen in out-of-memory conditions; for right now, while the patch is under early review, I suspect that's okay. So far I've come up with four possible ways to resolve this problem, which I will list here from least-likely to most-likely:
Of course, I'm open to suggestions of other approaches. (Not to mention patches!) Regarding your memory usage and "slice integers" comments, perhaps you'll be interested in the full lazy patch, which I hope to post later today. "Lazy concatenation" is only one of the features of the full patch; the other is "lazy slices". For a full description of my "lazy slices" implementation, see this posting (and the subsequent conversation) to Python-Dev: As for your final statement, I never claimed that this was a particularly clean design. I merely claim it makes things faster and is (so far) self-contained. For the Unicode versions of my lazy strings patches, the only files I touched were "Include/unicodeobject.h" and "Objects/unicodeobject.c". I freely admit my patch makes those files *even fussier* to work on than they already are. But if you don't touch those files, you won't notice the difference*, and the patch makes some Python string operations faster without making anything else slower. At the very least I suggest the patches are worthy of examination.
|
File Added: lch.py3k.unicode.lazy.concat.patch.53392.txt |
Attached below you will find the full "lazy strings" patch, which has both "lazy concatenation" and "lazy slices". The diff is against the current revision of the Py3k branch, bpo-53392. On my machine (Win32) rt.bat produces identical output before and after the patch, for both debug and release builds. As I mentioned in a previous comment, you can read the description (and ensuing conversation) about "lazy slices" here: One new feature of this version: I added a method on a Unicode string, s.simplify(), which forces the string to "render" if it's one of my exotic string subtypes (a lazy concatenation or lazy slice). My goal is to assuage fears about pathological memory-use cases where you have long-lived tiny slices of gigantic strings. If you realize you're having that problem, simply add calls to .simplify() on the slices and the problem should go away. As for the semantics of .simplify(), it returns a reference to the string s. Honestly I wasn't sure whether it should return a new string or just monkey with the existing string. Really, rendering doesn't change the string; it's the same string, with the exact same external behavior, just with different bits floating around underneath. For now it monkeys with the existing string, as that seemed best. (But I'd be happy to switch it to returning a new string if it'd help.) I had planned to make the "lazy slices" patch independent of the "lazy concatenation" patch. However, it wound up being a bigger pain that I thought, and anyway I figure the likelyhood that "lazy slices" would be accepted and "lazy concatenation" would not is effectively zero. So I didn't bother. If there's genuine interest in "lazy slices" without "lazy concatenation", I can produce such a thing. |
File Added: lch.py3k.unicode.lazy.concat.patch.53392.txt |
Just fixed the build under Linux--sorry, should have done that before posting the original patch. Patches now built and tested under Win32 and Linux, and produce the same output as an unpatched py3k trunk. lemburg: A minor correction: the full "lazy strings" patch (with "lazy slices") also touches "stringlib/partition.h", "stringlib/readme.txt", and "Objects/stringobject.c", in addition to the two unicodeobject.* files. The changes to these three files are minuscule, and don't affect their maintainability, so the gist of my statements still hold. (Besides, all three of those files will probably go away before Py3k ships.) |
I don't think that changing the possible return of PyUnicode_AS_UNICODE is reasonable. (option 1) Option 2 breaks the buffer interface. Option 3 severely limits the size of potential unicode strings. If you are only manipulating tiny unicode strings (8k?), then the effect of fast concatenation, slicing, etc., isn't terribly significant. Option 4 is possible, but I know I would feel bad if all of this work went to waste. Note what M. A. Lemburg mentioned. The functionality is useful, it's the polymorphic representation that is the issue. Rather than attempting to change the unicode representation, what about a wrapper type? Keep the base unicode representation simple (both Guido and M. A. have talked about this). Guido has also stated that he wouldn't be against views (slicing and/or concatenation) if they could be shown to have real use-cases. The use-cases you have offered here are still applicable, and because it wouldn't necessitate a (not insignificant) change in semantics and 3rd party code, would make it acceptable. |
josiahcarlson: I think you misunderstood options 2 and 3. The empty string (option 2) or As for writing a wrapper, I'm just not interested. I'm a strong believer For what it's worth, I came up with a fifth approach this morning while |
File Added: pybench.first.results.zip |
Problems so far:
a = []
while True:
x = u"x"*1000000
x = x[30:60] # Short slice of long string
a.append(x) If you can't do better than that, I'll have to reject it. PS I used your combined patch, if it matters. |
Thanks for taking the time!
Sorry about that; I'll fix it if I resubmit.
I tested on Windows and Linux, and I haven't seen that behavior. Which test_array, by the way? In Lib/test, or Lib/ctypes/test? Can you give me a stack trace to the segfault? With that I bet I
It matters. The combined patch has "lazy slices", the other When you say "grind to a halt" I'm not sure what you mean. When I ran that test, my Windows computer got to 1035 iterations Adding a call to .simplify() on the slice defeats this worst-case a = []
while True:
x = u"x"*1000000
x = x[30:60].simplify() # Short slice of long string
a.append(x) .simplify() forces lazy strings to render themselves. With that Failing that, is there any sort of last-ditch garbage collection Failing that, I could add garbage-collect-and-retry-once logic to And failing that, "lazy slices" are probably toast. It always was |
Here's another possible fix for the worst-case scenario: #define MAX_SLICE_DELTA (64*1024)
if ( ((size_of_slice + MAX_SLICE_DELTA) > size_of_original)
|| (size_of_slice > (size_of_original / 2)) )
use_lazy_slice();
else
create_string_as_normal(); You'd still get the full benefit of lazy slices most of the time, but it takes the edge off the really pathological cases. How's that? |
Sorry, the test_array failure was due to not rebuilding after patching. Because extension modules are built using distutils, they don't get automatically rebuilt when a relevant header has changed. "grind to a halt": swapping, probably, due to memory filling up with 1M-character string objects, as you experienced yourself. Your proposal takes the edge off, although I can still come up with a worst-case scenario (just use 64K strings instead of 1M strings, and leave the rest the same). I am far from convinced that replacing one pathological case (O(N**2) concatenation, which is easily explained and avoided) with another (which is harder to explain due to the more complicated algorithms and heuristics involved) is a good trade-off. This is all the worse since your optimization doesn't have a clear time/space trade-off: it mostly attempts to preserve time *and* space, but in the worst case it can *waste* space. (And I'm not convinced there can't be a pathological case where it is slower, too.) And the gains are dependent on the ability to *avoid* ultimately rendering the string; if every string ends up being rendered, there is no net gain in space, and there might be no net gain in time either (at least not for slices). I believe I would rather not pursue this patch further at this time; a far more important programming task is the str/unicode unification (now that the int/long unification is mostly there). If you want to clean up the patch, I suggest that you add a large comment section somewhere (unicode.h?) describing the algorithms in a lot of detail, including edge cases and performance analysis, to make review of the code possible. But you're most welcome to withdraw it, too; it would save me a lot of headaches. |
As discussed (briefly) over email, I'm moving this discussion back to the Python-3000 mailing list. But before I do I wanted to clear up something from your reply. "lazy concatenation" and "lazy slices" are really two patches, filed under the "lazy slices" penumbra. They are different optimizations, with different implementations and different behaviors. I implemented them cumulatively to save work because they intertwine when merged, but I had hoped they would be considered independently. I apologize if this point was unclear (and moreso if it was a bad idea). My reason for doing so: I suspected "lazy slices" were doomed from the start; doing the patch this way meant wasting less work. One downside of "lazy slices" is their ability to waste loads of memory in the worst-case. Now, "lazy concatenation" simply doesn't have that problem. Yet the fourth and fifth paragraphs of your most recent reply imply you think it can. A quick recap of lazy concatenation: The worst-case memory consumption behavior of lazy concatenation is adding lots and lots of tiny strings and never rendering; that will allocate lots of PyUnicodeConcatenationObjects. But it's nowhere near as bad as a short lazy slice of a long string. Does that make "lazy concatenation" more palatable? |
2 similar comments
As discussed (briefly) over email, I'm moving this discussion back to the Python-3000 mailing list. But before I do I wanted to clear up something from your reply. "lazy concatenation" and "lazy slices" are really two patches, filed under the "lazy slices" penumbra. They are different optimizations, with different implementations and different behaviors. I implemented them cumulatively to save work because they intertwine when merged, but I had hoped they would be considered independently. I apologize if this point was unclear (and moreso if it was a bad idea). My reason for doing so: I suspected "lazy slices" were doomed from the start; doing the patch this way meant wasting less work. One downside of "lazy slices" is their ability to waste loads of memory in the worst-case. Now, "lazy concatenation" simply doesn't have that problem. Yet the fourth and fifth paragraphs of your most recent reply imply you think it can. A quick recap of lazy concatenation: The worst-case memory consumption behavior of lazy concatenation is adding lots and lots of tiny strings and never rendering; that will allocate lots of PyUnicodeConcatenationObjects. But it's nowhere near as bad as a short lazy slice of a long string. Does that make "lazy concatenation" more palatable? |
As discussed (briefly) over email, I'm moving this discussion back to the Python-3000 mailing list. But before I do I wanted to clear up something from your reply. "lazy concatenation" and "lazy slices" are really two patches, filed under the "lazy slices" penumbra. They are different optimizations, with different implementations and different behaviors. I implemented them cumulatively to save work because they intertwine when merged, but I had hoped they would be considered independently. I apologize if this point was unclear (and moreso if it was a bad idea). My reason for doing so: I suspected "lazy slices" were doomed from the start; doing the patch this way meant wasting less work. One downside of "lazy slices" is their ability to waste loads of memory in the worst-case. Now, "lazy concatenation" simply doesn't have that problem. Yet the fourth and fifth paragraphs of your most recent reply imply you think it can. A quick recap of lazy concatenation: The worst-case memory consumption behavior of lazy concatenation is adding lots and lots of tiny strings and never rendering; that will allocate lots of PyUnicodeConcatenationObjects. But it's nowhere near as bad as a short lazy slice of a long string. Does that make "lazy concatenation" more palatable? |
Whoops, sorry. I refreshed a summary page I had lying around, which I guess re-posted the comment! Didn't mean to spam you with extra updates. |
Looks like I forgot to close and reject this. |
Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.
Show more details
GitHub fields:
bugs.python.org fields:
The text was updated successfully, but these errors were encountered: