Slow MP3 tag parsing/ByteVector::replace() performance

[Mathias Panzenböck]

Does this perform better than my solution (which is already in GIT)?
You have more allocations than I do (push_back to linked list), but I search twice. In O-Notation 
this should be equal, but of course it can differ in reality.

On 09/09/2011 11:03 AM, Henry Högelow wrote:
> Hi,
>
> I fixed the performance issues with ByteVector::replace for the Raumfeld devices with an algorithm
> allocating memory only once:
>
> ByteVector &ByteVector::replace(const ByteVector &pattern, const ByteVector &with)
> {
> if (pattern.size() == 0 || pattern.size() > size())
> return *this;
>
> const int patternSize = pattern.size();
> const int withSize = with.size();
>
> int offset = find(pattern);
>
> // try to not allocate memory for short buffers or rare patterns
> const size_t numDefaultStorageFields = 1024;
> size_t defaultStorageForPatternPositions[numDefaultStorageFields];
>
> // be prepared for any number of patterns
> typedef std::list<size_t> tPatternPositions;
> tPatternPositions morePatternPositions;
>
> size_t numPatternPositions = 0;
>
> while (offset >= 0)
> {
> if(numPatternPositions < numDefaultStorageFields)
> {
> defaultStorageForPatternPositions[numPatternPositions] = offset;
> }
> else
> {
> morePatternPositions.push_back(offset);
> }
> numPatternPositions++;
> offset = find(pattern, offset + patternSize);
> }
>
> if(numPatternPositions)
> {
> // we already know the resulting buffers size, so allocate it
> size_t newBuffersSize = size() + (withSize - patternSize) * numPatternPositions;
> ByteVector result(newBuffersSize);
>
> size_t readPos = 0;
> size_t writePos = 0;
>
> tPatternPositions::const_iterator itPos = morePatternPositions.begin();
>
> for (size_t i = 0; i < numPatternPositions; i++)
> {
> int patternPos = (i < numDefaultStorageFields) ? defaultStorageForPatternPositions[i] : *(itPos++);
>
> // copy stuff between patterns
> size_t numBytesInBetween = patternPos - readPos;
> ::memcpy(result.data() + writePos, data() + readPos, numBytesInBetween);
>
> readPos += numBytesInBetween;
> writePos += numBytesInBetween;
>
> // write the new pattern
> ::memcpy(result.data() + writePos, with.data(), withSize);
>
> // ignore the old pattern by advance the readPos
> readPos += patternSize;
> writePos += withSize;
> }
>
> // copy the rest
> ::memcpy(result.data() + writePos, data() + readPos, size() - readPos);
>
> // swap the data of result with our own
> std::swap(d, result.d);
> }
>
> return *this;
> }
>
>
> Best, Henry
>