15 Jun
2017
15 Jun
'17
11:43 p.m.
Dear all,
I would like to know your opinions about some optimizations
of Viterbi decoder, which were already discussed previously.
First of all, I would like to share some benchmarking results.
I used the test cases ("osmo-conv-test"), written by Tom Tsou,
to ensure that SIMD optimization is integrated correctly. And,
shortly speaking, the results are almost equal. Older version
of decoder is a little bit faster, but I think it's because
one is being compiled with "-march=native".
Returning back to the subject, as we allocate and free some
memory on every osmo_conv_decode_acc() call, what may happen
very frequently and tear down performance on some hardware,
there was the following suggestions:
1) Use static memory allocation where it's possible.
2) Use talloc for dynamic allocation.
3) Internal caching:
Fri May 9 18:23:03 UTC 2014, Tom Tsou wrote:
Internal caching was in the original implementation,
but
stripped from the submitted version mainly for simplicity
and avoiding the need for global variables, though we seem
to be having that discussion anyway ;-) The trellis values
can be cached based on pointer or hashed code. That works well
until threading is involved and cache access needs to be locked.
Those are features I need, but can probably be ignored in this
case.
Again, I think the API should be kept intact. Internal caching,
can be a topic for later discussion.
So, I am open for your ideas, opinions and remarks.
With best regards,
Vadim Yanitskiy.
16 Jun
16 Jun
8:06 a.m.
Hi Vadim,
On Fri, Jun 16, 2017 at 04:43:12AM +0700, Vadim Yanitskiy wrote:
I used the test cases ("osmo-conv-test"),
written by Tom Tsou,
to ensure that SIMD optimization is integrated correctly. And,
shortly speaking, the results are almost equal. Older version
of decoder is a little bit faster, but I think it's because
one is being compiled with "-march=native".
You can compile the new code with the same optimization flags (specified
in CFLAGS at configure time). We just simply cannot do -march=native as
a default, as that is not safe. But you can use that to verify your
assumption.
Returning back to the subject, as we allocate and free
some
memory on every osmo_conv_decode_acc() call, what may happen
very frequently and tear down performance on some hardware,
there was the following suggestions:
1) Use static memory allocation where it's possible.
That's generally what we do a lot in osmocom code. If it's predictable
how much memory a given process takes, we allocate that memory once
(statically or dynamically), use that all the time and then release it
once that process/procedure/instance is destroyed.
When I look at the current API, the decode_init()/decode_deinit()
functions are great candidates to perform such allocation/release of
memory. If applications use the osmo_conv_decode() convenience
wrapper, it simply means they don't care about efficiency, but if they
use the real init/scan/flush/deinit API, they would benefit from it.
Not sure if scan+flush should/could become one call for simplicity?
The viterbi.c code (which by the way chould be renamed to conv_acc.c or
the like) would then have to be restructured to plug into init/fini for
allocation+release.
2) Use talloc for dynamic allocation.
I doubt this will improve your speed. Feel free to try, but this is
more of a clean-up to ensure all the memory allocated within osmocom
projects is tracked/accounted for, and you can get talloc usage reports,
debug memory leaks, etc.
--
- Harald Welte <laforge(a)gnumonks.org> http://laforge.gnumonks.org/
============================================================================
"Privacy in residential applications is a desirable marketing option."
(ETSI EN 300 175-7 Ch. A6)
18 Jun
18 Jun
9:54 p.m.
Hi Harald,
When I look at the current API, the
decode_init()/decode_deinit()
functions are great candidates to perform such allocation/release of
memory. If applications use the osmo_conv_decode() convenience
wrapper, it simply means they don't care about efficiency, but if they
use the real init/scan/flush/deinit API, they would benefit from it.
You are talking about Sylvain's implementation of Viterbi,
which is currently used as fail-safe back-end for a new
algorithmically and SIMD optimized implementation, written
by Tom Tsou.
In the Sylvain's implementation (conv.c), init/scan/flush/deinit
are exposed for external usage, meanwhile Tom's implementation
is transparently integrated into the first one, and doesn't
expose anything outside.
The viterbi.c code (which by the way chould be renamed
to conv_acc.c or
the like) would then have to be restructured to plug into init/fini for
allocation+release.
Do you suggest to expose alloc_vdec, free_vdec and
osmo_conv_decode_acc like it is done in the conv.c?
Anyway, using init/fini is profitably only if you are doing
serial (en/de)coding of the same convolutional code. As soon
as you need to (en/de)code another convolutional code, you
will have to reallocate and reconfigure the vdec object.
(which by the way chould be renamed to conv_acc.c or
the like)
I like this idea, already in my TODO list :)
I doubt this will improve your speed. Feel free to
try, but this is
more of a clean-up to ensure all the memory allocated within osmocom
projects is tracked/accounted for, and you can get talloc usage
reports, debug memory leaks, etc.
Agree with you. But what do you think about talloc memory pools?
With best regards,
Vadim Yanitskiy.
10:13 p.m.
On Sun, Jun 18, 2017 at 12:54 PM, Vadim Yanitskiy <axilirator(a)gmail.com> wrote:
In the Sylvain's implementation (conv.c),
init/scan/flush/deinit
are exposed for external usage, meanwhile Tom's implementation
is transparently integrated into the first one, and doesn't
expose anything outside.
One note on API usage. Sylvain's init-deinit calls are exposed, but
I'm not aware of the those calls being used anywhere - only the
all-in-one version exists in osmo-bts.
So an API change on the init-deinit or alloc-dealloc of the decoder
object probably won't cause many dependency issues. But putting those
calls into use involves a large number of changes in the current
osmo-bts regardless of which implementation is used.
-TT
16 Jun
16 Jun
10:30 a.m.
Hi.
Microbenchmarking is nice but I'd like to know bigger picture: why do we need to
optimize current implementation further? Is it just for the sake of aesthetics and
fun of it? Do we have some profiling result showing that in scenario A Viterbi
decoder occupies XX% of the time?
Don't get me wrong - I'm not against optimizations, just would like to know more
about the general context.
On 15.06.2017 23:43, Vadim Yanitskiy wrote:
So, I am open for your ideas, opinions and remarks.
--
Max Suraev <msuraev(a)sysmocom.de> http://www.sysmocom.de/
=======================================================================
* sysmocom - systems for mobile communications GmbH
* Alt-Moabit 93
* 10559 Berlin, Germany
* Sitz / Registered office: Berlin, HRB 134158 B
* Geschaeftsfuehrer / Managing Director: Harald Welte
7:58 p.m.
Hi Vadim,
On Thu, Jun 15, 2017 at 2:43 PM, Vadim Yanitskiy <axilirator(a)gmail.com> wrote:
Returning back to the subject, as we allocate and free
some
memory on every osmo_conv_decode_acc() call, what may happen
very frequently and tear down performance on some hardware,
there was the following suggestions:
Max has a valid point of asking whether there is significant value in
further optimization when weighted against the cost of a non-trivial
API change. There are fielded deployments running the baseline code.
Will further optimization make a significant difference in those
cases? The answer is system and situation dependent; I can't answer
those questions in the general sense.
1) Use static memory allocation where it's
possible.
2) Use talloc for dynamic allocation.
3) Internal caching:
Persistent allocation is the best solution. Talloc will minimally
affect performance if at all. Internal caching is somewhat of a hack
to hide static allocation behind an API that does not allow it.
Fri May 9 18:23:03 UTC 2014, Tom Tsou wrote:
> Internal caching was in the original implementation, but
> stripped from the submitted version mainly for simplicity
> and avoiding the need for global variables, though we seem
> to be having that discussion anyway ;-) The trellis values
> can be cached based on pointer or hashed code. That works well
> until threading is involved and cache access needs to be locked.
> Those are features I need, but can probably be ignored in this
> case.
Three years ago, which feels like much longer, I was performing brute
force RNTI searches on LTE control channels. Convolutional decoding
was the limiting factor and maxed out multiple threads; every
optimization helped. That was a much different set of requirements.
-TT
18 Jun
18 Jun
10:25 p.m.
Hi Max and Tom,
why do we need to optimize current implementation
further?
Is it just for the sake of aesthetics and fun of it?
You are right, this is for the sake of aesthetics. I had a
task: to take some dead code from mailing lists, to make it
satisfy the Osmocom coding requirements and merge it part by
part. There was some warnings about object visibility (fixed),
about naming convention (fixed) and about memory allocation.
In the past, the discussion about memory allocation was set
aside, until code is merged. So, till now, this task remained
in my mind as some kind of unfinished work...
Do we have some profiling result showing that in
scenario
A Viterbi decoder occupies XX% of the time?
I am not sure that we can profile different parts of code
without actual modifications (probably perf can do that,
correct me otherwise). But we can profile a whole
implementation using the benchmark code from Tom, which
I mentioned before.
Don't get me wrong - I'm not against
optimizations,
just would like to know more about the general context.
It's ok, I am always happy to know your and other opinions :)
Persistent allocation is the best solution. Talloc
will minimally
affect performance if at all. Internal caching is somewhat of a hack
to hide static allocation behind an API that does not allow it.
I'll try to use persistent allocation where it's possible, e.g.
the struct vdecoder in osmo_conv_decode_acc() could be allocated
in the stack instead of heap.
Three years ago, which feels like much longer, I was
performing brute
force RNTI searches on LTE control channels. Convolutional decoding
was the limiting factor and maxed out multiple threads; every
optimization helped. That was a much different set of requirements.
Ok, that is exactly what I need to know.
Now I can let internal caching go, as it isn't critical for GSM.
With best regards,
Vadim Yanitskiy.
2515
days inactive
2518
days old
6 comments
4 participants
participants (4)
-
Harald Welte -
Max -
Tom Tsou -
Vadim Yanitskiy