| Message ID | 20170330143350.4420-1-lq@chinaffmpeg.org |
|---|---|
| State | Accepted |
| Commit | 99e5d81ef997cb88b1a40e6f253f37f7cbf251d9 |
| Headers | show |
Le decadi 10 germinal, an CCXXV, Steven Liu a écrit : > refer to: http://creativeandcritical.net/str-replace-c > add av_strreplace API for replace string operations. > > Signed-off-by: Steven Liu <lq@chinaffmpeg.org> > --- > libavutil/avstring.c | 77 ++++++++++++++++++++++++++++++++++++++++++++++++++++ > libavutil/avstring.h | 5 ++++ > 2 files changed, 82 insertions(+) It looks like it is duplicating a lot of functionality already implemented in BPrint. I suggest you try implementing it using BPrint instead. Regards,
2017-03-31 17:51 GMT+08:00 Nicolas George <george@nsup.org>: > Le decadi 10 germinal, an CCXXV, Steven Liu a écrit : > > refer to: http://creativeandcritical.net/str-replace-c > > add av_strreplace API for replace string operations. > > > > Signed-off-by: Steven Liu <lq@chinaffmpeg.org> > > --- > > libavutil/avstring.c | 77 ++++++++++++++++++++++++++++++ > ++++++++++++++++++++++ > > libavutil/avstring.h | 5 ++++ > > 2 files changed, 82 insertions(+) > > It looks like it is duplicating a lot of functionality already > implemented in BPrint. I suggest you try implementing it using BPrint > instead. > I think just similar, not duplicating, and the simple functionality use BPrint maybe too complex. > > Regards, > > -- > Nicolas George > _______________________________________________ > ffmpeg-devel mailing list > ffmpeg-devel@ffmpeg.org > http://ffmpeg.org/mailman/listinfo/ffmpeg-devel >
2017-03-31 20:11 GMT+08:00 Steven Liu <lingjiujianke@gmail.com>: > > > 2017-03-31 17:51 GMT+08:00 Nicolas George <george@nsup.org>: > >> Le decadi 10 germinal, an CCXXV, Steven Liu a écrit : >> > refer to: http://creativeandcritical.net/str-replace-c >> > add av_strreplace API for replace string operations. >> > >> > Signed-off-by: Steven Liu <lq@chinaffmpeg.org> >> > --- >> > libavutil/avstring.c | 77 ++++++++++++++++++++++++++++++ >> ++++++++++++++++++++++ >> > libavutil/avstring.h | 5 ++++ >> > 2 files changed, 82 insertions(+) >> >> It looks like it is duplicating a lot of functionality already >> implemented in BPrint. I suggest you try implementing it using BPrint >> instead. >> > I think just similar, not duplicating, and the simple functionality use > BPrint maybe too complex. > >> >> Regards, >> >> -- >> Nicolas George >> _______________________________________________ >> ffmpeg-devel mailing list >> ffmpeg-devel@ffmpeg.org >> http://ffmpeg.org/mailman/listinfo/ffmpeg-devel >> > > Pushed Thanks！
Le primidi 11 germinal, an CCXXV, Steven Liu a écrit : > I think just similar, not duplicating, and the simple functionality use > BPrint maybe too complex. Well, I will say it unambiguously: Parts of this patch DO duplicate logic that we already have, and your statement about BPrint being too complex is simply completely wrong. Therefore, it was not acceptable as is and should not have been pushed. Pushing while leaving only half a day to answer this was UNACCEPTABLE. Do not ever do it again please. Now, I will not insist on reverting, but I will demand that you make a priority of simplifying this code. Regards,
2017-04-01 16:01 GMT+08:00 Nicolas George <george@nsup.org>: > Le primidi 11 germinal, an CCXXV, Steven Liu a écrit : > > I think just similar, not duplicating, and the simple functionality use > > BPrint maybe too complex. > > Well, I will say it unambiguously: > > Parts of this patch DO duplicate logic that we already have, and your > statement about BPrint being too complex is simply completely wrong. > Ok, Can you guide me to improve it please? > > Therefore, it was not acceptable as is and should not have been pushed. > > Pushing while leaving only half a day to answer this was UNACCEPTABLE. > Do not ever do it again please. > > Now, I will not insist on reverting, but I will demand that you make a > priority of simplifying this code. > > Regards, > > -- > Nicolas George > > _______________________________________________ > ffmpeg-devel mailing list > ffmpeg-devel@ffmpeg.org > http://ffmpeg.org/mailman/listinfo/ffmpeg-devel > >
On Sat, 1 Apr 2017 10:01:15 +0200 Nicolas George <george@nsup.org> wrote: > Le primidi 11 germinal, an CCXXV, Steven Liu a écrit : > > I think just similar, not duplicating, and the simple functionality use > > BPrint maybe too complex. > > Well, I will say it unambiguously: > > Parts of this patch DO duplicate logic that we already have, and your > statement about BPrint being too complex is simply completely wrong. The bprint API is somewhat complicated. > Therefore, it was not acceptable as is and should not have been pushed. > > Pushing while leaving only half a day to answer this was UNACCEPTABLE. > Do not ever do it again please. Why get upset over a simple function being added? Lots of unreviewed patches or patches that were half-approved or not really approved get pushed. That's how this project work. If you don't like it, propose a rule change. > Now, I will not insist on reverting, but I will demand that you make a > priority of simplifying this code. It's already maximally self-contained.
On 2017-04-01 13:12 +0200, wm4 wrote: > On Sat, 1 Apr 2017 10:01:15 +0200 > Nicolas George <george@nsup.org> wrote: [...] > > Therefore, it was not acceptable as is and should not have been pushed. > > > > Pushing while leaving only half a day to answer this was UNACCEPTABLE. > > Do not ever do it again please. > > Why get upset over a simple function being added? > > Lots of unreviewed patches or patches that were half-approved or not > really approved get pushed. That's how this project work. If you don't > like it, propose a rule change. I do not think a rule change is needed for this case at hand. While it is probably true that there were patches that didn't have enough review before they were pushed, it is not at all common, that patches which are the subject of an active discussion, as it was in this case, just get pushed. Additionally this patch adds public API which should be sufficiently discussed because reverting soon becomes difficult and involved. [...] Alexander
On Sat, 1 Apr 2017 22:34:26 +0200 Alexander Strasser <eclipse7@gmx.net> wrote: > On 2017-04-01 13:12 +0200, wm4 wrote: > > On Sat, 1 Apr 2017 10:01:15 +0200 > > Nicolas George <george@nsup.org> wrote: > [...] > > > Therefore, it was not acceptable as is and should not have been pushed. > > > > > > Pushing while leaving only half a day to answer this was UNACCEPTABLE. > > > Do not ever do it again please. > > > > Why get upset over a simple function being added? > > > > Lots of unreviewed patches or patches that were half-approved or not > > really approved get pushed. That's how this project work. If you don't > > like it, propose a rule change. > > I do not think a rule change is needed for this case at hand. > > While it is probably true that there were patches that didn't have enough > review before they were pushed, it is not at all common, that patches > which are the subject of an active discussion, as it was in this case, > just get pushed. > > Additionally this patch adds public API which should be sufficiently > discussed because reverting soon becomes difficult and involved. Especially for someone new this is not obvious. Either have clear rules, or don't hand out push rights like free cookies to inexperienced project members (and then complain that they make use of it). I requested that the rules be clarified a while ago, but nobody cared, and a patch attempting to improve the description of the existing rules and practice was not accepted. In the case at hand, Steven Liu might have pushed a bit too early, but it's not like he ignored Nicolas George's post. Also I encouraged him to separate this function and move it to libavutil, and nobody had anything against it all that time (until Nicolas George objected later). So I don't see a terrible offense here. Again, if you don't like this, make the damn rules clearer.
Le decadi 10 germinal, an CCXXV, Steven Liu a écrit : > refer to: http://creativeandcritical.net/str-replace-c > add av_strreplace API for replace string operations. > > Signed-off-by: Steven Liu <lq@chinaffmpeg.org> > --- > libavutil/avstring.c | 77 ++++++++++++++++++++++++++++++++++++++++++++++++++++ > libavutil/avstring.h | 5 ++++ > 2 files changed, 82 insertions(+) > > diff --git a/libavutil/avstring.c b/libavutil/avstring.c > index 1787a1ef54..52e6e6cd13 100644 > --- a/libavutil/avstring.c > +++ b/libavutil/avstring.c > @@ -231,6 +231,83 @@ int av_strncasecmp(const char *a, const char *b, size_t n) > return c1 - c2; > } > > +char *av_strreplace(const char *str, const char *from, const char *to) Before starting: Steven, you seem not completely familiar with the English language. Sometimes, I make complex sentences. If you need, ask and I will rephrase. First, I think the "strreplace" name should have been reserved for the case-sensitive version, using possibly strireplace for the case-insensitive version. Since it was only applied very recently, and is not yet used even in the rest of FFmpeg, I say we fix the name right now. (Note: that does not mean this minute, that means this week, leaving a chance for other to give their opinion. And of course, you yourself are allowed to disagree.) Second, I notice quite a few potential integer overflows. They would need to be fixed if the code is to stay that way. Fortunately, I think we can get rid of all that. Third, and most important for the rest of my discourse: this code is guilty of the sin of premature optimization. It builds a rather complex cache mechanism, but possibly cripples it by introducing an arbitrary limit, and more importantly, it uses av_stristr() repeatedly; av_stristr() itself is not optimized at all, and there are further optimizations for repeated use with the same needle; see the Knuth-Morris-Pratt algorithm. Keep that in mind if anything I write below seems "less efficient" than what is already there. I told that it duplicated the BPrint API, I was wrong: the API it duplicates dynarray. But it could have been BPrint, and they are the same anyway. Because there are three obvious ways of implementing this function. 1. (the present implementation) Find and keep track of all occurrences of the needle, allocate the target string with the exact size, and build it. 2. Find and count all occurrences of the needle, allocate the target string with the exact size, and then re-find all occurrences of the needle to build it. 3. Build the target string on the fly. (Lexicon: strstr(haystack, needle): to find a needle in a haystack.) By itself, the simplest solution to implement in C is #2 because it uses only a single dynamic allocation and very simple loops. It requires twice as much needle searches, but if they are optimized it may well be a non-issue. Solution #1 addresses the "twice as much needle searches" issue by storing the results. I believe it is a very bad idea, because storing the results requires a rather complex dynamic reallocation mechanism: in this code, the dynamic array to store the results is about one third of the whole code, and most of the integer overflows. One of the av_dynarray API can make it simpler, but it is still a little tricky to use. And I suspect it is not even worth the effort; only a benchmark could tell: premature optimization. I say: let us NOT use solution #1. Solution #3 takes a completely different road. To implement it in plain C would require the same kind of tricky dynamic reallocation as solution #1, for the target string instead of the positions. But we have the BPrint API that makes it very simple. My advice would be: go with solution #3, and if performance is a problem start by implementing KMP. If per chance you prefer solution #2, you can achieve it by removing all the "cache"-related code and replacing access to the "cache" with a new call to av_stristr(). > +{ > + /* Adjust each of the below values to suit your needs. */ > + /* Increment positions cache size initially by this number. */ > + size_t cache_sz_inc = 16; > + /* Thereafter, each time capacity needs to be increased, > + * multiply the increment by this factor. */ > + const size_t cache_sz_inc_factor = 3; > + /* But never increment capacity by more than this number. */ > + const size_t cache_sz_inc_max = 1048576; > + uintptr_t *pos_cache_tmp, *pos_cache = NULL; > + size_t cache_sz = 0; > + /* Increase the cache size when necessary. */ > + if (cache_sz < count) { > + cache_sz += cache_sz_inc; > + pos_cache_tmp = av_realloc(pos_cache, sizeof(*pos_cache) * cache_sz); > + if (!pos_cache_tmp) { > + goto end_strreplace; > + } else pos_cache = pos_cache_tmp; > + cache_sz_inc *= cache_sz_inc_factor; > + if (cache_sz_inc > cache_sz_inc_max) { > + cache_sz_inc = cache_sz_inc_max; > + } > + } > + pos_cache[count-1] = pstr2 - str; > + pstr = pstr2 + fromlen; All this is the code needed to keep track of the positions of the needle. One way or another, it must go away. > + retlen = orglen + (tolen - fromlen) * count; This is a potential integer overflow, for example. > + /* Otherwise, duplicate the string whilst performing > + * the replacements using the position cache. */ > + pret = ret; > + memcpy(pret, str, pos_cache[0]); > + pret += pos_cache[0]; > + for (i = 0; i < count; i++) { > + memcpy(pret, to, tolen); > + pret += tolen; > + pstr = str + pos_cache[i] + fromlen; > + cpylen = (i == count-1 ? orglen : pos_cache[i+1]) - pos_cache[i] - fromlen; > + memcpy(pret, pstr, cpylen); > + pret += cpylen; > + } If there are n copies of the needle, there are n+1 pieces of string around them, and one of them has to be taken out of the loop. This version isolates the one before the first needle. It would have been much simpler to isolate the one after the last needle. The formula for cpylen, in particular, is a symptom of this non-optimal choice. The loop could look that way: while (needle) { copy from pos to needle update pos add replacement string } copy from pos to the end The BPrint version is actually exactly the same: av_bprint_init() while (needle) { av_bprint_append_data() to copy from pos to needle update pos av_bprint_append_data() to add the replacement string } av_bprint_append_data() to copy from pos to the end av_bprint_is_complete() to check malloc errors av_print_finalize() All in all, I think the BPrint version is the easiest to implement right now. Regards,
2017-04-02 17:41 GMT+08:00 Nicolas George <george@nsup.org>: > Le decadi 10 germinal, an CCXXV, Steven Liu a écrit : > > refer to: http://creativeandcritical.net/str-replace-c > > add av_strreplace API for replace string operations. > > > > Signed-off-by: Steven Liu <lq@chinaffmpeg.org> > > --- > > libavutil/avstring.c | 77 ++++++++++++++++++++++++++++++ > ++++++++++++++++++++++ > > libavutil/avstring.h | 5 ++++ > > 2 files changed, 82 insertions(+) > > > > diff --git a/libavutil/avstring.c b/libavutil/avstring.c > > index 1787a1ef54..52e6e6cd13 100644 > > --- a/libavutil/avstring.c > > +++ b/libavutil/avstring.c > > @@ -231,6 +231,83 @@ int av_strncasecmp(const char *a, const char *b, > size_t n) > > return c1 - c2; > > } > > > > > +char *av_strreplace(const char *str, const char *from, const char *to) > > Before starting: Steven, you seem not completely familiar with the > English language. Sometimes, I make complex sentences. If you need, ask > and I will rephrase. > > First, I think the "strreplace" name should have been reserved for the > case-sensitive version, using possibly strireplace for the > case-insensitive version. > > Since it was only applied very recently, and is not yet used even in the > rest of FFmpeg, I say we fix the name right now. > > (Note: that does not mean this minute, that means this week, leaving a > chance for other to give their opinion. And of course, you yourself are > allowed to disagree.) > > Second, I notice quite a few potential integer overflows. They would > need to be fixed if the code is to stay that way. Fortunately, I think > we can get rid of all that. > > Third, and most important for the rest of my discourse: this code is > guilty of the sin of premature optimization. It builds a rather complex > cache mechanism, but possibly cripples it by introducing an arbitrary > limit, and more importantly, it uses av_stristr() repeatedly; > av_stristr() itself is not optimized at all, and there are further > optimizations for repeated use with the same needle; see the > Knuth-Morris-Pratt algorithm. Keep that in mind if anything I write > below seems "less efficient" than what is already there. > > I told that it duplicated the BPrint API, I was wrong: the API it > duplicates dynarray. But it could have been BPrint, and they are the > same anyway. > > Because there are three obvious ways of implementing this function. > > 1. (the present implementation) Find and keep track of all occurrences > of the needle, allocate the target string with the exact size, and > build it. > > 2. Find and count all occurrences of the needle, allocate the target > string with the exact size, and then re-find all occurrences of the > needle to build it. > > 3. Build the target string on the fly. > > (Lexicon: strstr(haystack, needle): to find a needle in a haystack.) > > By itself, the simplest solution to implement in C is #2 because it uses > only a single dynamic allocation and very simple loops. It requires > twice as much needle searches, but if they are optimized it may well be > a non-issue. > > Solution #1 addresses the "twice as much needle searches" issue by > storing the results. I believe it is a very bad idea, because storing > the results requires a rather complex dynamic reallocation mechanism: in > this code, the dynamic array to store the results is about one third of > the whole code, and most of the integer overflows. One of the > av_dynarray API can make it simpler, but it is still a little tricky to > use. And I suspect it is not even worth the effort; only a benchmark > could tell: premature optimization. > > I say: let us NOT use solution #1. > > Solution #3 takes a completely different road. To implement it in plain > C would require the same kind of tricky dynamic reallocation as solution > #1, for the target string instead of the positions. But we have the > BPrint API that makes it very simple. > > My advice would be: go with solution #3, and if performance is a problem > start by implementing KMP. > > If per chance you prefer solution #2, you can achieve it by removing all > the "cache"-related code and replacing access to the "cache" with a new > call to av_stristr(). > > > > +{ > > + /* Adjust each of the below values to suit your needs. */ > > + /* Increment positions cache size initially by this number. */ > > + size_t cache_sz_inc = 16; > > + /* Thereafter, each time capacity needs to be increased, > > + * multiply the increment by this factor. */ > > + const size_t cache_sz_inc_factor = 3; > > + /* But never increment capacity by more than this number. */ > > + const size_t cache_sz_inc_max = 1048576; > > > + uintptr_t *pos_cache_tmp, *pos_cache = NULL; > > + size_t cache_sz = 0; > > > + /* Increase the cache size when necessary. */ > > + if (cache_sz < count) { > > + cache_sz += cache_sz_inc; > > + pos_cache_tmp = av_realloc(pos_cache, sizeof(*pos_cache) * > cache_sz); > > + if (!pos_cache_tmp) { > > + goto end_strreplace; > > + } else pos_cache = pos_cache_tmp; > > + cache_sz_inc *= cache_sz_inc_factor; > > + if (cache_sz_inc > cache_sz_inc_max) { > > + cache_sz_inc = cache_sz_inc_max; > > + } > > + } > > + pos_cache[count-1] = pstr2 - str; > > + pstr = pstr2 + fromlen; > > All this is the code needed to keep track of the positions of the > needle. One way or another, it must go away. > > > + retlen = orglen + (tolen - fromlen) * count; > > This is a potential integer overflow, for example. > > > + /* Otherwise, duplicate the string whilst performing > > + * the replacements using the position cache. */ > > + pret = ret; > > + memcpy(pret, str, pos_cache[0]); > > + pret += pos_cache[0]; > > + for (i = 0; i < count; i++) { > > + memcpy(pret, to, tolen); > > + pret += tolen; > > + pstr = str + pos_cache[i] + fromlen; > > + cpylen = (i == count-1 ? orglen : pos_cache[i+1]) - > pos_cache[i] - fromlen; > > + memcpy(pret, pstr, cpylen); > > + pret += cpylen; > > + } > > If there are n copies of the needle, there are n+1 pieces of string > around them, and one of them has to be taken out of the loop. This > version isolates the one before the first needle. It would have been > much simpler to isolate the one after the last needle. The formula for > cpylen, in particular, is a symptom of this non-optimal choice. The loop > could look that way: > > while (needle) { > copy from pos to needle > update pos > add replacement string > } > copy from pos to the end > > The BPrint version is actually exactly the same: > > av_bprint_init() > while (needle) { > av_bprint_append_data() to copy from pos to needle > update pos > av_bprint_append_data() to add the replacement string > } > av_bprint_append_data() to copy from pos to the end > av_bprint_is_complete() to check malloc errors > av_print_finalize() > > All in all, I think the BPrint version is the easiest to implement right > now. > I'm not sure if i misunderstand, but i will try to do it with your suggestion. I will try to understand BPrint and try to use it. > > Regards, > > -- > Nicolas George > > _______________________________________________ > ffmpeg-devel mailing list > ffmpeg-devel@ffmpeg.org > http://ffmpeg.org/mailman/listinfo/ffmpeg-devel > >
diff --git a/libavutil/avstring.c b/libavutil/avstring.c index 1787a1ef54..52e6e6cd13 100644 --- a/libavutil/avstring.c +++ b/libavutil/avstring.c @@ -231,6 +231,83 @@ int av_strncasecmp(const char *a, const char *b, size_t n) return c1 - c2; } +char *av_strreplace(const char *str, const char *from, const char *to) +{ + /* Adjust each of the below values to suit your needs. */ + /* Increment positions cache size initially by this number. */ + size_t cache_sz_inc = 16; + /* Thereafter, each time capacity needs to be increased, + * multiply the increment by this factor. */ + const size_t cache_sz_inc_factor = 3; + /* But never increment capacity by more than this number. */ + const size_t cache_sz_inc_max = 1048576; + + char *pret, *ret = NULL; + const char *pstr2, *pstr = str; + size_t i, count = 0; + uintptr_t *pos_cache_tmp, *pos_cache = NULL; + size_t cache_sz = 0; + size_t cpylen, orglen, retlen, tolen, fromlen = strlen(from); + + /* Find all matches and cache their positions. */ + while ((pstr2 = av_stristr(pstr, from))) { + count++; + /* Increase the cache size when necessary. */ + if (cache_sz < count) { + cache_sz += cache_sz_inc; + pos_cache_tmp = av_realloc(pos_cache, sizeof(*pos_cache) * cache_sz); + if (!pos_cache_tmp) { + goto end_strreplace; + } else pos_cache = pos_cache_tmp; + cache_sz_inc *= cache_sz_inc_factor; + if (cache_sz_inc > cache_sz_inc_max) { + cache_sz_inc = cache_sz_inc_max; + } + } + + pos_cache[count-1] = pstr2 - str; + pstr = pstr2 + fromlen; + } + orglen = pstr - str + strlen(pstr); + /* Allocate memory for the post-replacement string. */ + if (count > 0) { + tolen = strlen(to); + retlen = orglen + (tolen - fromlen) * count; + } else { + retlen = orglen; + } + ret = av_malloc(retlen + 1); + if (!ret) { + goto end_strreplace; + } + + if (!count) { + /* If no matches, then just duplicate the string. */ + av_strlcpy(ret, str, retlen + 1); + } else { + /* Otherwise, duplicate the string whilst performing + * the replacements using the position cache. */ + pret = ret; + memcpy(pret, str, pos_cache[0]); + pret += pos_cache[0]; + for (i = 0; i < count; i++) { + memcpy(pret, to, tolen); + pret += tolen; + pstr = str + pos_cache[i] + fromlen; + cpylen = (i == count-1 ? orglen : pos_cache[i+1]) - pos_cache[i] - fromlen; + memcpy(pret, pstr, cpylen); + pret += cpylen; + } + ret[retlen] = '\0'; + } + +end_strreplace: + /* Free the cache and return the post-replacement string, + * which will be NULL in the event of an error. */ + av_free(pos_cache); + return ret; +} + const char *av_basename(const char *path) { char *p = strrchr(path, '/'); diff --git a/libavutil/avstring.h b/libavutil/avstring.h index dd2876990f..33be8bf484 100644 --- a/libavutil/avstring.h +++ b/libavutil/avstring.h @@ -266,6 +266,11 @@ int av_strcasecmp(const char *a, const char *b); */ int av_strncasecmp(const char *a, const char *b, size_t n); +/** + * Locale-independent strings replace. + * @note This means only ASCII-range characters are replace + */ +char *av_strreplace(const char *str, const char *from, const char *to); /** * Thread safe basename.
refer to: http://creativeandcritical.net/str-replace-c add av_strreplace API for replace string operations. Signed-off-by: Steven Liu <lq@chinaffmpeg.org> --- libavutil/avstring.c | 77 ++++++++++++++++++++++++++++++++++++++++++++++++++++ libavutil/avstring.h | 5 ++++ 2 files changed, 82 insertions(+)