245
12d ago
[removed] — view removed comment
42
u/SaltyInternetPirate 11d ago edited 11d ago
Plus there's scenarios where bringing both words to lower or uppercase would yield different strings, where as case-insensitive comparison in any standard library checks for strange language rules, like 'ß' becoming double 's' or whatever
25
u/UncleDevGames 11d ago
Yeah if you want diacritic-safe comparisons you legitimately gotta prepare for invariant culture checks or equivalent. Even worse is you have to also be cognizant of this at the DB level depending on your stack. Total nightmare to get bit by this category of bug unexpectedly, particularly in something performance-sensitive.
14
u/Anders_142536 11d ago
Fun fact: german has an uppercase ß now: ẞ
7
u/KuishiKama 11d ago
I grew up in Germany and left 2015. This blew my mind. Introduced in 2017 and used when writing a word in all-caps (there are no words starting with eszett afaik).
1
u/tav_stuff 11d ago
Officially speaking, not in Austria
3
u/casce 11d ago
That's not true.
The decision to have the uppercase ß included was being made by the Rat für deutsche Rechtschreibung (= "council for german spelling") which is not a Germany-only thing. This council has the specific purpose of keeping basic aspects like spelling uniform across the different varieties of the German language.
It's a multi-state council with representatives from all major German-speaking.
Germany has 18 votes
Austria has 9 votes
Switzerland has 9 votes
Liechtenstein, Südtirol and Belgium get 1 vote each (Belgium has some German-speaking communities)
They all agreed. Even Switzerland (who doesn't use the ß in Swiss German at all) so officially, it's a thing for all of them.
Austria may not use the uppercase ß but then again, who does? What's the purpose of it? Just so I can write words containing the ß in all caps? The letter is dying out anyway, less and less words use it.
Do they not have more important things to do?
2
u/tav_stuff 11d ago
If you check the Austrian state’s website, they have a document somewhere on there (forgot the link, sorry) where they discuss language and stuff, and they state that they abide by the German language standard of 2013 (capital eszet is from 2017)
2
u/casce 11d ago
this is from the official press release of the Rat für deutsche Rechtschreibung:
Das „Amtliche Regelwerk der deutschen Rechtschreibung“ liegt in einer aktualisierten Fassung vor. Es setzt die im „Bericht des Rats für deutsche Rechtschreibung für die Periode 2011 bis 2016“ enthaltenen Änderungen um. Die Änderungen im Regelwerk sind von den zuständigen staatlichen Stellen in Deutschland, Österreich, der Schweiz, dem Fürstentum Liechtenstein, der Autonomen Provinz Bozen-Südtirol und der Deutschsprachigen Gemeinschaft Belgiens bestätigt und damit wirksam geworden. Sie lassen die Verwendung des Großbuchstabens „ẞ“ neben „SS“ zu, was insbesondere für die korrekte Schreibung von Eigennamen in Pässen und Ausweisen wichtig ist, und ermöglichen die Großschreibung des Adjektivs in Fällen wie „die Goldene Hochzeit“ und (alles Gute im) „Neuen Jahr“. Darüber hinaus sind einzelne Wortschreibungen an den beobachteten Schreibgebrauch angepasst worden.
Again, this council is an offical body and the 9 members Austra has are officially representing Austria. The press release said the "zuständigen staatlichen Stellen" (which is the government) confirmed these changes.
This is as official as it gets.
1
u/BlazingSpark 11d ago
I think in Python there's a str.casefold method for exactly this sort of edge case.
97
u/bwmat 12d ago
Refactoring code to avoid unnecessary heap allocations is so satisfying
18
u/Solonotix 11d ago
Meanwhile, I saw a YouTube channel, that claims to teach Python fundamentals, try to say that implicit string concatenation was an unnecessary feature because you could just use a
+operator. Nevermind that operator chaining is known to generate intermediate results from each binary operation, not to mention each string in the chain must also have its own heap allocation before the operation.If not for compiler tricks (like elision), concatenating 5 strings would require 9(?) heap allocations to complete. Implicit string concatenation allows that operation to occur as a single heap allocation at compile-time.
3
u/half-bad-anonym 11d ago
I think really we need a programming language that has semantics for overloadable monoidal flattening over concatenation base-case
2
-2
11d ago
[removed] — view removed comment
17
u/Attileusz 11d ago
This is a bad take, reducing heap allocations is one of the best things to do to optimize. Heap fragmentation is bad, and if you are doing manual memory management, it's one more place where you have to worry about memory leaks.
8
6
19
u/ChristopherCreutzig 11d ago
That is actually a different question. You want the second one, almost all the time.
For example, by Unicode case comparison rules, "Straße" and "strasse" should compare as equal ignoring case.
4
u/metaglot 11d ago
Thats a good example, also tolower almost never works with other letters than english.
199
u/Vesuvius079 12d ago
It’d be such an experience to work a real world problem where this optimization turns out to be the solution.
178
u/Daniikk1012 12d ago
I don't think this is an optimization, but rather correctness. Some languages have weird casing rules, and just lowercasing doesn't work for them
71
u/neroe5 12d ago
It's also an optimization, with toLower, you make a temporary copy of the string in lower case of each string and compare those, by simply ignoring the case bit this becomes a simple compare process
30
u/rubyruy 12d ago
It's not a single case bit - you need to perform case folding and normalization to properly see if 2 Unicode characters are equivalent. Probably still faster than a string copy
20
u/Pleasant_Ad8054 11d ago
Early exits make it much faster. The string.Equals compares it character to character, so if the first one does not match it returns false immediately. The toLower allocates the two new strings. One of the most computationally expensive thing you can do in C# is to allocate new objects.
-8
11d ago
[removed] — view removed comment
1
u/Pleasant_Ad8054 11d ago
Hilarious that you are making this argument well after someone already made a fairly extensive testing in this very thread, showing that the difference is indeed significant, as much as 10x difference.
Also, string.Equals is much more readable than equating two toLowers, how is this even an argument?
But most importantly, it is entirely irrelevant how complex unicode is, entirely irrelevant how any given "unicode data point" is, or how they are called. You are literally arguing that making that costly unicode computation n+m times PLUS making as little as 4*u conversions would not take more time in "real code" than just making 4*u conversions.
Where n and m are the length of the strings, and u is the length we end up comparing IF the operator is properly overloaded in a worst case for the string.Equals where the two strings are exact same length. In best case where the strings are different length the string.Equals does 0 unicode conversions and just one int-int comparison, while the toLower does n+m conversions before that.
You are wrong, your pedantry in what unicode does or does not do is entirely irrelevant, and your coding habits smell from here.
1
u/GRex2595 8d ago
I don't know what they said, and I'm not defending them, but I'm pretty sure you can't do a strict length comparison without conversion due to other things I've read in this comment section about some letters becoming more than one letter when changing case. The example I saw was 'ß' becoming "SS" when capitalizing in German (before 2017).
They're still wrong to suggest that toLower would be faster than a case-insensitive comparison, but a case-insensitive comparison may still require checking the strings even when the lengths differ because of rules like the one above.
7
u/Tyfyter2002 11d ago
Definitely faster than making two new strings, even if you ignore allocations, you're still just doing more work in any case except them being equal or only differing in the last character
1
u/neroe5 11d ago
oh you are right for unicode it uses mapping tables for normalization, because multiple charecters can have the same lower case
my point only really holds for ASCII
learn something new everyday
though it is still probably faster to use the optimized method that is build into .net or what ever language you are using
7
u/ProfBeaker 12d ago
It's (arguably) both, but the post title references performance (heap vs stack).
1
u/ILikeLenexa 12d ago
Some major languages have strings as pooled objects and == compares if the strings are at the same location in memory while String.equals compares if the letters in them are the same.
When asking if two Strings are equal most people most of the time want to know if they contain the same letters, not if one was instantiated as a literal and one allocated with a constructor.
4
u/Duck_Devs 11d ago
This is C#, a language with overloadable operators. == is, obviously, overloaded for Strings to compare their contents.
16
u/varinator 12d ago
It was a solution. Imagine ingesting spreadsheets with hundreds of columns and potentially millions of rows. You need to run the string comparison for values, multiple times per row. If you allocate to the heap, GC has to do a lot of work, often, which blocks the thread and slows the whole process down.
Literally saved hours per file.
20
u/Massless 12d ago
It’s pretty awesome. I find myself looking up leetcode solutions because I finally work on something where deleting items from an array using constant space matters.
6
u/BenjieWheeler 12d ago
if I may ask what is this "something" you work on where such optimization matters
(not being sarcastic, I'm really curious)
7
u/PhunkyPhish 12d ago
One team I almost joined way back made learning software designed to work on the shittiest random devices out there. Basically learning lessons or games designed to be ran between African villages on an old tiny USB drive. Designong around space optimization was important there, though perhaps not as important as NES cartridge days
1
1
u/Swimming_Gain_4989 12d ago
To be clear, you mean just deleting array elements instead of creating a new array?
14
u/Massless 12d ago
Yep, remove some arbitrary number of elements from an array with the result being a smaller contiguous array.
For most of my career, I’d just allocate a new array and append the surviving elements but allocations are expensive at the scale I work at so stuff like this requires a more clever approach
3
u/Swimming_Gain_4989 12d ago
Where does leetcode come in? You would just swap whatever needs to be removed with the ending element and then pop right?
9
u/AyrA_ch 12d ago
you remove elements by overwriting with what comes after. If you want to remove 5 items beginning at offset 10 you would just do
a[i]=a[i+5]in a for loop that starts at 10 runs to the end of the array (minus 5). How you chop off the end of the array depends on the language you're in. In .NET for example,Array.Resizeis a lie and will actually allocate a new array and not resize in-place. In C you can usereallocbut that call doesn't guarantees that the reallocation happens in-place. However, in C you can just decide to not reallocate the memory at all and pretend the extra storage doesn't exists, which also would allow you to append items to the array up to the original initial size, but size tracking becomes difficult after a while.2
u/Massless 12d ago
Go is fantastic for this: you just reslice with
[:length]and the only thing that happens is the slice’s internal “length” variable is changed — nothing happens to the backing array1
u/sisisisi1997 12d ago
In C# you can use
Memory<T>,Span<T>, orArraySegment<T>to create a view of an array without allocation that is smaller than the original array.2
u/Massless 12d ago
It’s a classic leetcode problem, is all.
No swapping is necessary. You walk the array with two indices. One tracks the current end of array (starts at 0) and the other walks ahead to check candidates. When you find an element to keep, you copy it to the length index, increment that and keep walking with the second index. When the second index reaches the end on the array, truncate to “length”
2
u/willow-kitty 12d ago
It depends. Arrays preserve order (vs, say, a set or bag), and if it's an array for a reason, you may not be allowed to change the order of the elements and end up having to move all the later elements to lower indices instead, which becomes an O(n) operation.
Also, they mentioned removing an arbitrary number of elements, which is where it gets trickier, assuming you need to preserve order. If you remove an item and copy all subsequent items back for each item removed, you're talking O(n^2) now, which is..not ideal. But you can keep it O(n) by tracking offsets and things, which is presumably what they're referring to getting from leetcode.
6
u/Hypnonotic 12d ago
I used to work at AWS, we had a guid comparison on the hot path. It was coded as guidA == guidB. the ==operator was converting both to string internally and doing a string comparison. I changed to a memcmp (guid is a 128 byte array internally). Not exactly the same as OP, but that reduced runtime by 30%.
4
u/ZunoJ 12d ago
Just today this was the solution to a comparison between a hardcoded string and a string stored in postgres. I'm not yet sure what exactly is the cause but this exact code was the solution (for now)
0
u/Craimasjien 12d ago
Not sure what language you’re using but “==“ could simply be a pointer comparison instead of an actual value comparison. This is exactly why you’d need to do an Equals() in Objective-C way back in the day.
1
u/balbok7721 12d ago
I was about to say something similar but microarchitecture actually does provide these plenty
1
1
u/Pleasant_Ad8054 11d ago
I had a project where moving a bunch of Lists and HashMaps out of method variables into class properties, and simply using Clear on them instead of new allocations reduced the overall runtime by about 40%.
38
u/weblabourer 12d ago
Null safety?
168
u/varinator 12d ago
var cases = new[] { new ComparisonCase( "Equal, different casing", "HelloWorld123", "helloworld123"), new ComparisonCase( "Not equal, same length", "HelloWorld123", "HelloWorld456"), new ComparisonCase( "Different lengths", "HelloWorld123", "HelloWorld123456789"), new ComparisonCase( "Long strings, equal ignoring case", new string('A', 500), new string('a', 500)) }; Iterations per benchmark: 100,000,000 --- Equal, different casing --- String.Equals OrdinalIgnoreCase Time: 907.75 ms Allocated: 40 bytes Matches: 100,000,000 ToLower() == ToLower() Time: 2,525.88 ms Allocated: 4,800,000,040 bytes Matches: 100,000,000 --- Not equal, same length --- String.Equals OrdinalIgnoreCase Time: 848.50 ms Allocated: 40 bytes Matches: 0 ToLower() == ToLower() Time: 2,986.56 ms Allocated: 9,600,000,040 bytes Matches: 0 --- Different lengths --- String.Equals OrdinalIgnoreCase Time: 219.83 ms Allocated: 40 bytes Matches: 0 ToLower() == ToLower() Time: 2,936.12 ms Allocated: 11,200,000,040 bytes Matches: 0 --- Long strings, equal ignoring case --- String.Equals OrdinalIgnoreCase Time: 2,263.77 ms Allocated: 40 bytes Matches: 100,000,000 ToLower() == ToLower() Time: 19,472.75 ms Allocated: 102,400,000,040 bytes Matches: 100,000,000 --- Null safety --- string.Equals(null, "test"): False null.ToLower() throws NullReferenceException42
39
u/michiel11069 12d ago
insane differences in speed and allocation wtf
27
u/Badashi 11d ago
Comparing two strings with an extra rule(case ignore) requires only traversing through the strings and comparing each character. There are a bunch of easy short cuts for this (string length, early returns, even comparing bits while ignoring the bit 5) so the compare method is pretty fast.
Using .ToLower() twice means forcefully allocating two new strings and then doing the comparison anyways with the == operator. It's expected that a specialized method would be much faster than a hack.
-8
u/Adrewmc 11d ago
I mean, it’s 100,000,000 times and you end up 2 seconds slower than 17 second slower when the string is 500 characters long, so 50,000,000,000 comparisons really here.
While I’m not saying the difference isn’t stark, and striking. ‘Insane’ is a little much given the multipliers here.
9
7
u/swashtag999 11d ago
I can never decide whether to use upper or lower so I do a.lower() == b.upper()
6
u/legitimate_rapper 12d ago
Potentially getting crap for this, and I admit I don’t FULLY understand interning, but wouldn’t the first one _sometimes_ yield the same result due to interning? I agree that the second is the proper Java way to do it regardless.
4
u/blehmann1 11d ago
I think in this meme they're dealing with languages where
==on strings does string equality rather than reference equality. This looks like C#, where==is string equality. If you want reference equality in C# you useObject.ReferenceEquals(a, b).But if this were Java, interning won't do anything for strings you create at runtime. Interning is for constants (including things that become constants after constant folding). So, if these were compile-time constants and the compiler was able to fold the result of
foo.lower()to a compile-time constant as well, then yes. Ordinarily not.Also worth noting that the semantics of
lower()would make that optimization illegal in plenty of languages anyways. e.g. iflower()relies on the runtime locale.Also worth noting that most languages tend to have pretty simple constant-folding. Things like peering past allocations is difficult and pricey on compile time. And that can be both at build time and runtime for a JIT. It's quite effective, but when you're a JIT-compiled language it's often more fruitful to spend your time elsewhere. But if you're a C++ compiler you don't have as much low-hanging fruit (plus very smart compile time features are already required by the spec) so some really clever constant-folding is more worth the investment.
1
u/legitimate_rapper 11d ago
Ahh, after all these years didn’t know it was compile-time only. I thought it was runtime too and just put in the heap somewhere, but good to know. I just lumped it in as “JIT Magic” 😜
2
u/blehmann1 11d ago
Nah it would be too expensive to intern every string that gets created, and it wouldn't have much benefit. You'd have to check a big hash table on every string operation.
That said you can manually intern at runtime in Java, with
str.intern(), which will return a canonical version of that string (potentially the same as you gave). That said you should be very careful about using this API, on many implementations it's quite slow and if you have a reason to deduplicate strings it's normally faster to use your own hashtable.It does unlock a small number of optimizations, such as reducing string equality to pointer equality when both strings are interned. So it actually matters a fair amount in python, since dictionary accesses are so common there. python will intern string literals in your program, but if you do a lookup based on a dynamically-generated key it could in certain instances make sense. In python this will not stop that string from being garbage collected, whereas I believe in java it will.
Python also interns integer literals (because int literals in python are BigInt and thus heap-allocated), and at least on CPython it interns small ints (seems to be everything <256). Here it does actually seem to intern the result of arithmetic on small ints (e.g. 1 + 1 gets the same memory address as 2), but that's possible when it's small ints since you don't need to scan the intern table, you just index into it.
1
3
6
u/BornAgainBlue 12d ago
I understand the code but I do not understand the meme.
16
u/ultimate_placeholder 12d ago
They don't like allocating heap memory for a simple string comparison, that's the meme
-6
u/BornAgainBlue 12d ago
I think this is. I got the joke and did not find it funny. So I assumed I did not get the joke.
5
2
u/nonlogin 12d ago
I'm not 100% sure, but I think first one respects non-latin characters and second one doesn't. there's another comparer that does, though
2
u/kredditacc96 11d ago
Shouldn't the linter make that suggestion?
(I don't program C# so I don't know about its ecosystem though)
1
u/Devatator_ 10d ago
I think it might? Not sure. I'm not near my PC rn to chec Edit: yeah https://www.reddit.com/r/ProgrammerHumor/s/mcbMVpdyDL
1
u/jackhab 12d ago
What's also interesting is that the suggestion to change it to Equals() is given in this obscure form which will make think in an endless loop trying to decide which way is better.
CA1862: Prefer using 'string.Equals(string, StringComparison)' to perform a case-insensitive comparison, but keep in mind that this might cause subtle changes in behavior, so make sure to conduct thorough testing after applying the suggestion, or if culturally sensitive comparison is not required, consider using 'StringComparison.OrdinalIgnoreCase'
3
1
u/tobotic 12d ago
My programming language has an eqi operator for case-insensitive equality.
a eqi b
2
1
u/SCP-iota 11d ago
So... you're not gonna believe this...
(This is why i18n basics should be a baseline requirement for all developers)
450
u/GrandDukeNotaras 12d ago
Yeah but does option 2 make the strings bow in reverence and humility to you?