D12659: two new UDS structures

[David Faure]

dfaure added a comment.


  Thanks for that investigation. Interesting that linear search is faster than binary search in the same data structure... maybe the compiler optimizes it better? Did you profile V2 to find out where the time is spent, or do you have a better explanation?
  But even if both were equal performance-wise I'd favor linear search because sorted insertion is easy to get wrong - as this patch shows ;)
  
  When you say "scales better", we're talking about the number of fields in the udsentry, not the number of items. But kioslaves don't fill in 1000 fields, so I have the feeling that scaling with the number of fields isn't a requirement.
  
  Are those benchmarks run in Release (or RelWithDebInfo) mode, rather than Debug (which is a big no no for benchmarks)? Qt should be compiled with optimizations enabled too.
  
  PS: for all alternatives where the API is the same, we could use a template function (templated on the type of UDSEntry implementation) to perform the tests; this would ensure that all tests are actually testing the same thing ;-)

INLINE COMMENTS

> udsentry_benchmark.cpp:464
> +    {
> +        inline Field() : m_index(-1) {}
> +        inline Field(const uint index, const QString &value) : m_str(value), m_long(0), m_index(index) {}

m_long should be initialized too (in-place initialized in the member declaration would help not forgetting that)

> udsentry_benchmark.cpp:468
> +        // This operator is essential to gain some speed, because the default == is slow
> +        inline bool operator == (const Field &other) {
> +            return m_index == other.m_index;

const

> udsentry_benchmark.cpp:487
> +            {
> +                *index = Field(field, value);
> +                return;

wouldn't it be faster to assign to index->m_str here?

  index->m_str = value;

> udsentry_benchmark.cpp:491
> +        }
> +        storage.append(Field(field, value));
> +    }

std::vector with emplace_back would be interesting here, performance-wise.

If you keep using QVector, though, then Q_DECLARE_MOVABLE(Field) would help, especially when reserving too small.

> udsentry_benchmark.cpp:498
> +            {
> +                *index = Field(field, value);
> +                return;

wouldn't it be faster to assign to index->m_long here?

  index->m_long = value;

> udsentry_benchmark.cpp:510
> +    {
> +        for (auto index = storage.constBegin(), end = storage.constEnd(); index != end; ++index) {
> +            if (index->m_index == field)

alternative: std::find_if.

> udsentry_benchmark.cpp:560
> +        entry.stringValue(KIO::UDSEntry::UDS_GROUP) == entry2.stringValue(KIO::UDSEntry::UDS_GROUP);
> +        QCOMPARE(equal, true);
> +    }

QVERIFY(equal)

> udsentry_benchmark.cpp:593
> +        // This operator is essential to gain some speed, because the default == is slow
> +        inline bool operator == (const Field &other) {
> +            return m_index == other.m_index;

const

> udsentry_benchmark.cpp:619
> +        }
> +        storage.append(Field(field, value));
> +    }

This relies on insert being called in ascending "field" order, for lower_bound to work.
But that is not necessarily the case in kioslaves, so you'd have to insert at "index" here, instead of appending.

> udsentry_benchmark.cpp:634
> +    }
> +    QString stringValue(uint field)
> +    {

const

> udsentry_benchmark.cpp:642
> +    }
> +    long long numberValue(uint field, long long defaultValue = -1)
> +    {

const

REPOSITORY
  R241 KIO

REVISION DETAIL
  https://phabricator.kde.org/D12659

To: jtamate, dfaure, #frameworks
Cc: michaelh, bruns
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.kde.org/pipermail/kde-frameworks-devel/attachments/20180502/bc9a5440/attachment.html>