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

[Henry Högelow]

Hi,

> 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.

I did not profile against your solution. But for most use cases you should  
not find more than 1024 occurrences of the search pattern, so you will  
have only one allocation.

Best, Henry

>
> 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
>>
>
> _______________________________________________
> taglib-devel mailing list
> taglib-devel at kde.org
> https://mail.kde.org/mailman/listinfo/taglib-devel
>


-- 
Erstellt mit Operas revolutionärem E-Mail-Modul: http://www.opera.com/mail/