Discussion:
[omniORB] performance problem increasing sequence length in a loop
Michael Teske
2008-11-06 22:57:29 UTC
Permalink
Hello!

We're trying (again) to port our system from Orbacus to omniORB. Unfortunately we
have lots of code where sequences are resized dynamically, sometimes even in a
loop (I know this is not the best style, but to find all these locations could
become a nightmare).
While something like this is very fast in Orbacus it becomes very slow in omniORB.
I think this isbecause Orbcaus doubles the reserved buffer if the new desired
length is lower than the old length * 2, while omniORB just allocates the new
length and copies the old sequence over *every* time.

To make my point clear, here's a test program:


---- snip ----

#ifdef USE_OMNIORB
#include <omniORB4/CORBA.h>
#else
#include <OB/CORBA.h>
#endif

#include <iostream>

typedef void (*testfunc)(void) ;

void timetestfunc(testfunc fun, const char * message )
{
clock_t start = clock();
fun();
clock_t stop = clock();
std::cout << message << " took " << (stop-start) / (CLOCKS_PER_SEC / 1000) <<
"ms \n";
}

long prealloc = 0;
void sequencetest()
{
CORBA::StringSeq_var ret = new CORBA::StringSeq(prealloc);
for (int i = 0; i < 40000; i++) {
long index = ret->length();
ret->length(index+1);
}
}

int main(void)
{
prealloc = 0;
timetestfunc(sequencetest, "sequencetest_no_prealloc");
prealloc = 40000;
timetestfunc(sequencetest, "sequencetest_prealloc = 40000");

return 0;
}


---- snip ----


Output omniorb:
sequencetest_no_prealloc took 7090ms
sequencetest_prealloc = 40000 took 0ms

output orbacus:
sequencetest_no_prealloc took 10ms
sequencetest_prealloc = 40000 took 0ms

this was on linux on a 2,8 GHz single-core i86.

The effect is even bigger on self-defined sequences.

Are there any plans to change this or do I have to live with that?
Or, if just nobody bothered yet, are there any reasons not to change this
allocation strategy? If not I would consider writing a patch...

Greetings,
Michael
Duncan Grisby
2008-11-07 20:24:10 UTC
Permalink
Post by Michael Teske
We're trying (again) to port our system from Orbacus to
omniORB. Unfortunately we have lots of code where sequences are
resized dynamically, sometimes even in a loop (I know this is not the
best style, but to find all these locations could become a nightmare).
While something like this is very fast in Orbacus it becomes very slow
in omniORB. I think this isbecause Orbcaus doubles the reserved
buffer if the new desired length is lower than the old length * 2,
while omniORB just allocates the new length and copies the old
sequence over *every* time.
You're right -- omniORB does not currently increase sequence buffers in
an incremental way, so code that repeatedly increases the length by one
will be O(n^2).

I'd welcome patches that implement a more efficient growth scheme. Make
sure your patches follow the existing code style.

Cheers,

Duncan.
--
-- Duncan Grisby --
-- ***@grisby.org --
-- http://www.grisby.org --
Arne Pajunen
2008-11-19 15:45:59 UTC
Permalink
Post by Duncan Grisby
Post by Michael Teske
We're trying (again) to port our system from Orbacus to
omniORB. Unfortunately we have lots of code where sequences are
resized dynamically, sometimes even in a loop (I know this is not the
best style, but to find all these locations could become a nightmare).
While something like this is very fast in Orbacus it becomes very slow
in omniORB. I think this isbecause Orbcaus doubles the reserved
buffer if the new desired length is lower than the old length * 2,
while omniORB just allocates the new length and copies the old
sequence over *every* time.
You're right -- omniORB does not currently increase sequence buffers in
an incremental way, so code that repeatedly increases the length by one
will be O(n^2).
I'd welcome patches that implement a more efficient growth scheme. Make
sure your patches follow the existing code style.
Cheers,
Duncan.
Hi,

We actually noticed almost the exact same issue in our system after
porting it from Orbacus to omniORB. I wrote a small patch that changes
the allocator for the common sequence base types to double the old
length until sufficient for new desired length.

I'm not sure if this is good enough for inclusion in the main omniORB
tree, since its not the best possible allocation scheme. Its also not
configurable and i didn't look too hard if I caught all the cases where
the allocated buffer is resized, but some might find it a useful
workaround for the issue. It fixed the performance issues we were
experiencing.

If someone wants to make a cleaner patch based on this, you're more than
welcome to do so. I would be most interested in a permanent fix.

Best regards,

Arne Pajunen
Software Developer
OpenTTCN Oy, Finland
-------------- next part --------------
diff -ru omniORB-4.1.3-clean/include/omniORB4/seqTemplatedecls.h omniORB-4.1.3/include/omniORB4/seqTemplatedecls.h
--- omniORB-4.1.3-clean/include/omniORB4/seqTemplatedecls.h 2006-04-28 21:40:46.000000000 +0300
+++ omniORB-4.1.3/include/omniORB4/seqTemplatedecls.h 2008-11-14 18:31:57.297326400 +0200
@@ -155,7 +155,11 @@
// Allocate buffer on-demand. Either pd_data == 0
// or pd_data = buffer for pd_max elements
if (!pd_buf || len > pd_max) {
- copybuffer(((len > pd_max) ? len : pd_max));
+ _CORBA_ULong new_length = (pd_max == 0 ? len : pd_max);
+ if (len > new_length) {
+ while (new_length < len) new_length = new_length*2;
+ }
+ copybuffer(new_length);
}
}
pd_len = len;
@@ -1109,7 +1113,11 @@
// Allocate buffer on-demand. Either pd_data == 0
// or pd_data = buffer for pd_max elements
if (!pd_buf || len > pd_max) {
- copybuffer(((len > pd_max) ? len : pd_max));
+ _CORBA_ULong new_length = (pd_max == 0 ? len : pd_max);
+ if (len > new_length) {
+ while (new_length < len) new_length = new_length*2;
+ }
+ copybuffer(new_length);
}
}

@@ -1899,7 +1907,11 @@
// Allocate buffer on-demand. Either pd_data == 0
// or pd_data = buffer for pd_max elements
if (!pd_data || len > pd_max) {
- copybuffer(((len > pd_max) ? len : pd_max));
+ _CORBA_ULong new_length = (pd_max == 0 ? len : pd_max);
+ if (len > new_length) {
+ while (new_length < len) new_length = new_length*2;
+ }
+ copybuffer(new_length);
}
}

diff -ru omniORB-4.1.3-clean/include/omniORB4/stringtypes.h omniORB-4.1.3/include/omniORB4/stringtypes.h
--- omniORB-4.1.3-clean/include/omniORB4/stringtypes.h 2005-11-17 19:03:27.000000000 +0200
+++ omniORB-4.1.3/include/omniORB4/stringtypes.h 2008-11-14 18:31:29.950526400 +0200
@@ -634,7 +634,11 @@
// Allocate buffer on-demand. Either pd_data == 0
// or pd_data = buffer for pd_max elements
if (!pd_data || len > pd_max) {
- copybuffer(((len > pd_max) ? len : pd_max));
+ _CORBA_ULong new_length = (pd_max == 0 ? len : pd_max);
+ if (len > new_length) {
+ while (new_length < len) new_length = new_length*2;
+ }
+ copybuffer(new_length);
}
}
pd_len = len;
diff -ru omniORB-4.1.3-clean/include/omniORB4/valueTemplatedecls.h omniORB-4.1.3/include/omniORB4/valueTemplatedecls.h
--- omniORB-4.1.3-clean/include/omniORB4/valueTemplatedecls.h 2007-04-19 01:32:43.000000000 +0300
+++ omniORB-4.1.3/include/omniORB4/valueTemplatedecls.h 2008-11-14 18:31:38.748926400 +0200
@@ -467,7 +467,11 @@
// Allocate buffer on-demand. Either pd_data == 0
// or pd_data = buffer for pd_max elements
if (!pd_data || len > pd_max) {
- copybuffer(((len > pd_max) ? len : pd_max));
+ _CORBA_ULong new_length = (pd_max == 0 ? len : pd_max);
+ if (len > new_length) {
+ while (new_length < len) new_length = new_length*2;
+ }
+ copybuffer(new_length);
}
}

diff -ru omniORB-4.1.3-clean/include/omniORB4/wstringtypes.h omniORB-4.1.3/include/omniORB4/wstringtypes.h
--- omniORB-4.1.3-clean/include/omniORB4/wstringtypes.h 2005-11-17 19:03:27.000000000 +0200
+++ omniORB-4.1.3/include/omniORB4/wstringtypes.h 2008-11-14 18:31:45.940526400 +0200
@@ -610,7 +610,11 @@
// Allocate buffer on-demand. Either pd_data == 0
// or pd_data = buffer for pd_max elements
if (!pd_data || len > pd_max) {
- copybuffer(((len > pd_max) ? len : pd_max));
+ _CORBA_ULong new_length = (pd_max == 0 ? len : pd_max);
+ if (len > new_length) {
+ while (new_length < len) new_length = new_length*2;
+ }
+ copybuffer(new_length);
}
}
pd_len = len;

Loading...