search

DLR-SC / tixi

A simple XML interface library
Apache License 2.0
35 stars 16 forks source link

Computational complexity of tixiAddFloatVector #183

Closed kieh-da closed 2 years ago

kieh-da commented 3 years ago

tixiAddFloatVector appears to have a computational complexity of n² (n being the number of elements in the vector), where a complexity of n should suffice. The figure below was created using Matlab R2019a with Tixi 3.1.1 (64 bit) to run tixiAddFloatVector with varying vector size n.

measured_time_tixiAddFloatVector

rainman110 commented 2 years ago

Thanks for the interesting analysis. I agree, this should be linear and a runtime of more than a second is not acceptable.

I'll try to figure out, where the runtime is spent.

rainman110 commented 2 years ago

I can confirm the behaviour!

The major time is spent at the string concatenation (i.e. the conversion of the vector to the string) in the current line: https://github.com/DLR-SC/tixi/blob/master/src/tixiImpl.c#L1561

rainman110 commented 2 years ago

I exchanged strcat with snprintf with the appropriate concat position, and I managed to achieve linear scaling.

Using 10^5 element, I could reduce the runtime from 59 seconds down to 150 millisconds.

rainman110 commented 2 years ago

I managed a further runtime improvement by a factor of 2. The upper test now just takes 67 ms (originally 59 seconds) using a vector of 10^5 elements.

kieh-da commented 2 years ago

That's quite an improvement! Thanks for fixing the issue.