bxparks
commented
3 years ago I'm not on the Arduino team, but I'm leaving a drive-by comment because this PR touches on 2 things that are interesting to me: APIs and code efficiency. This PR has problems with both.
API:
The String class is a fundamental part of the Arduino API. It is included in every 3rd party Arduino Core that I am aware of (e.g. ESP8266, ESP32, STM32duino, Teensyduino, etc). If new methods are added to the AVR version of the String class, then it would break cross-platform compatibility. In other words, any end-user application that used the new methods would compile only on the AVR platform, and break on every other platform. This would be a terrible result.
This problem is not unique to this PR: any change to the Arduino API has to consider the impact on the overall ecosystem, and the change has to be significantly advantageous to be worth breaking cross-platform compatibility. I don't think that the features provided by padStart() and padEnd() to the String class is compelling enough to make this breakage because they can be implemented as external library code, with the following signatures:
String padStart(const String& s, unsigned totalLength, char pad);
String padEnd(const String& s, unsigned totalLength, char pad);The advantage of an external library is that this code will be compatible with other 3rd party platforms.
Efficiency:
The implementation given in this PR has significant performance problems, particularly the padStart() method. It performs repeated copies of the intermediate string for each iteration that adds a pad character. (In algorithmic complexity theory, this is an O(M * N) algorithm instead of an O(M + N) algorithm.) It also uses repeated allocation on the heap, which can cause heap fragmentation problems. Some quick benchmarking with a string of ~60 characters, with totalLength of 200 shows that padStart() can be 10X slower than padEnd().
Alternative 1:
Here is one alternative that is about 20X faster for padStart() and about 2X faster for padEnd(). The key here is to use the String::reserve() to allocate the resulting string only once:
String padStartFast(const String& s, unsigned totalLength, char pad)
{
if (totalLength <= s.length()) return s;
unsigned paddingLength = totalLength - s.length();
String result;
result.reserve(totalLength);
while (paddingLength--) {
result += pad;
}
result += s;
return result;
}
String padEndFast(const String& s, unsigned totalLength, char pad)
{
if (totalLength <= s.length()) return s;
unsigned paddingLength = totalLength - s.length();
String result;
result.reserve(totalLength);
result = s;
while (paddingLength--) {
result += pad;
}
return result;
}Even with a 20X and 2X improvement in speed, we can do better. One limitation of the above code comes from the inefficient implementation of the String::concat(char c) method in WString.cpp, which causes a strcpy() to be called on every iteration of adding a pad character. But even if we rewrote concat(char c) to avoid a strcpy() (for example, see https://github.com/arduino/ArduinoCore-avr/pull/97 which was rejected), we gain only about a 1.7X speed improvement according to my benchmarks. Overall, I think I agree with the rejection of https://github.com/arduino/ArduinoCore-avr/pull/97, because we can do far far better with Alternative 2 below.
Alternative 2:
This code avoids the overhead of the String::concat() on each iteration by precomputing the padding string, then calling concat() just once. My benchmarks say that this version is 100X faster than the original version of padStart(), and 10X faster than the original version of padEnd() (using the example string I tested; different strings will give different efficiency results):
String padStartFaster(const String& s, unsigned totalLength, char pad)
{
if (totalLength <= s.length()) return s;
unsigned paddingLength = totalLength - s.length();
String result;
result.reserve(totalLength); // reserve early to avoid heap fragmentation
char* buffer = new char[paddingLength + 1];
char* p = buffer;
while (paddingLength--) {
*p++ = pad;
}
*p = '\0';
result += buffer;
result += s;
delete[] buffer;
return result;
}
String padEndFaster(const String& s, unsigned totalLength, char pad)
{
if (totalLength <= s.length()) return s;
unsigned paddingLength = totalLength - s.length();
String result;
result.reserve(totalLength); // reserve early to avoid heap fragmentation
char* buffer = new char[paddingLength + 1];
char* p = buffer;
while (paddingLength--) {
*p++ = pad;
}
*p = '\0';
result += s;
result += buffer;
delete[] buffer;
return result;
}The problem with Alternative 2 is that it performs an extra heap allocation for the precomputed buffer, which means it consumes more memory than Alternative 1. On microcontrollers with only a small amount of memory, this could be a problem, and Alternative 1 might be better on those platforms.
(Edit: It occurred to me that the while() loop above can be replaced with a single call to memset(buffer, pad, paddingLength). My benchmarks say that memset() makes no difference on the lower end microcontrollers (AVR, SAMD21). It was ~20% faster on ESP8266, ESP32, and Teensy 3.2. But ~10% slower on the STM32, no idea why.)
Recommendation
Since Alternative 1 and Alternative 2 provide slightly different trade-off decisions between time and space, I think the reasonable thing to do is to create a library that provides both alternatives, and let the consumer of the library choose the version that makes sense for them. Only the application developer will know which version is most appropriate for the given microcontroller and the given application.
I also recommend unit testing these functions, because I haven't. It is too easy to make "off-by-one" and other such errors.
The other recommendation is to avoid the String class in most situations, especially on lower-end AVR controllers with only a small amount of static memory. The risk of heap fragmentation is too high. The vast majority of programs/sketches that I write, like 98% of them, do not use the String class.
asukiaaa
I want to use padding method on Arduino like javascript. Could you consider adding these methods?
References
By the way, Arduino framework supports
dependsoption so is there any plan to separateStringas a library?Thank you.