logarithmic time performance

[davidenitti]

Dear,
I am comparing Blog with my language, and I noticed a logarithmic behavior of the time performance of BLOG.
For example, if I use 1000 samples it takes 0.6 s, if I use 10000 samples it takes 1.5 s (instead of 0.6x10=6), if I use 100000 samples it takes 5.7 s (instead of 1.5x10=15). (excluding parsing time.)
I would aspect that the time is linear with respect to the number of samples.
do you use parallelization? If so, is there a way to avoid this and use only 1 thread?
is there another reason for this behavior?

[jxwuyi]

Hi,

What model are you using?

davidenitti notifications@github.com于2015年6月18日星期四写道：

Dear,
I am comparing Blog with my language, and I noticed a logarithmic behavior
of the time performance of BLOG.
For example, if I use 1000 samples it takes 0.6 s, if I use 10000 samples
it takes 1.5 s (instead of 0.6x10=6), if I use 100000 samples it takes 5.7
s (instead of 1.5x10=15). (excluding parsing time.)
I would aspect that the time is linear with respect to the number of
samples. It also seems that there is no parallelization (initialization
excluded). Am I right?
can you give an explanation of this?

—
Reply to this email directly or view it on GitHub
#337.

[davidenitti]

id-uncert-det.blog

The time given the number of samples is logarithmic below 20000 samples then becomes linear. this is really strange.
this happens also for other models, e.g., burglary.blog
I tried to force BLOG to use of a single CPU, it gets a bit slower, but the logarithmic behavior remains.

[cberzan]

You're right that the runtime should be linear in the number of samples. I suspect the non-linear runtime you're seeing with small number of samples is because of data structure / JIT overhead. When you run with more samples, this overhead becomes less pronounced, and you see linear runtime.

We don't do explicit parallelism / multithreading in either BLOG or DBLOG. You may see multiple cores being used, but that's because of parallelism in the JVM, not in our code.