[Bluez-devel] sbc decoder unrolled

[Bluez-devel] sbc decoder unrolled

[Brad Midgley]

Hey

woohoo... I worked over the decoder a lot more and finally unrolled & 
committed it. It still uses floating point for now.

I was very proud of the fact that I found a way to rotate which 
sbc_proto_x_x0 value we choose rather than shifting matrixed values 
around in every loop. It's even more clear that the implementation they 
illustrate in the spec is meant to make the algorithm clear but not be 
an efficient way to do it.

I don't know how the instruction cache size in arm compares to x86. I 
haven't checked to see yet if unrolling is as big a win on xscale. fwiw, 
it cut x86 cpu use by about 50% over the looped code.

I'll look at fixed point next.

Brad


-------------------------------------------------------
SF.Net email is Sponsored by the Better Software Conference & EXPO
September 19-22, 2005 * San Francisco, CA * Development Lifecycle Practices
Agile & Plan-Driven Development * Managing Projects & Teams * Testing & QA
Security * Process Improvement & Measurement * http://www.sqe.com/bsce5sf
_______________________________________________
Bluez-devel mailing list
Bluez-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bluez-devel

RE: [Bluez-devel] sbc decoder unrolled

[Victor Shcherbatyuk]

Brad,

I'll check if I can do the same for the encoder, getting rid of that
array shifting might speed up the stuff (well, it will probably add some
array index operations which might make things worse, but we will see).

Regards,
    Victor.

-----Original Message-----
From: bluez-devel-admin@lists.sourceforge.net
[mailto:bluez-devel-admin@lists.sourceforge.net] On Behalf Of Brad
Midgley
Sent: Friday, September 09, 2005 7:37 AM
To: BlueZ Mailing List
Subject: [Bluez-devel] sbc decoder unrolled

Hey

woohoo... I worked over the decoder a lot more and finally unrolled &
committed it. It still uses floating point for now.

I was very proud of the fact that I found a way to rotate which
sbc_proto_x_x0 value we choose rather than shifting matrixed values
around in every loop. It's even more clear that the implementation they
illustrate in the spec is meant to make the algorithm clear but not be
an efficient way to do it.

I don't know how the instruction cache size in arm compares to x86. I
haven't checked to see yet if unrolling is as big a win on xscale. fwiw,
it cut x86 cpu use by about 50% over the looped code.

I'll look at fixed point next.

Brad


-------------------------------------------------------
SF.Net email is Sponsored by the Better Software Conference & EXPO
September 19-22, 2005 * San Francisco, CA * Development Lifecycle
Practices Agile & Plan-Driven Development * Managing Projects & Teams *
Testing & QA Security * Process Improvement & Measurement *
http://www.sqe.com/bsce5sf
_______________________________________________
Bluez-devel mailing list
Bluez-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bluez-devel


This e-mail message contains information which is confidential and may be=
 privileged. It is intended for use by the addressee only. If you are not=
 the intended addressee, we request that you notify the sender immediatel=
y and delete or destroy this e-mail message and any attachment(s), withou=
t copying, saving, forwarding, disclosing or using its contents in any ot=
her way. TomTom N.V., TomTom International BV or any other company belong=
ing to the TomTom group of companies will not be liable for damage relati=
ng to the communication by e-mail of data, documents or any other informa=
tion.


-------------------------------------------------------
SF.Net email is Sponsored by the Better Software Conference & EXPO
September 19-22, 2005 * San Francisco, CA * Development Lifecycle Practices
Agile & Plan-Driven Development * Managing Projects & Teams * Testing & QA
Security * Process Improvement & Measurement * http://www.sqe.com/bsce5sf
_______________________________________________
Bluez-devel mailing list
Bluez-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bluez-devel

Re: [Bluez-devel] sbc decoder unrolled

[Steven Singer]

Brad Midgley wrote:
>                       It's even more clear that the implementation they 
> illustrate in the spec is meant to make the algorithm clear but not be 
> an efficient way to do it.

This is definitely true.

The spec allows you complete flexibility on your implementation. You're
not even obliged to use the algorithm in the spec. You need make sure
only that the errors between the outputs of your encoder and decoder and
the outputs of the reference encoder and decoder are less than a
threshold. (For qualification, they talk about the decoder having a K
value which needs to be greater than 14).

If you have a program that can calculate K, then I suggest that a
suitable regression test is to measure the K values of the reference
test inputs between:

  output of reference encoder + reference decoder

and each of:

  output of reference encoder + your decoder (spec requires K > 14)
  output of your encoder + reference decoder
  output of your encoder + your decoder

This gives you much more optimisation flexibility than requiring an
identical output bit stream.

As well as measuring K, you should also listen to the outputs -
otherwise you may have a bug that sounds bad but somehow manages to
pass the K test.

Remember SBC is a lossy codec, it'd be pointless to try too hard to
precisely reproduce the losses of the reference codec.

	- Steven
-- 


**********************************************************************
This email and any files transmitted with it are confidential and
intended solely for the use of the individual or entity to whom they
are addressed. If you have received this email in error please notify
the system manager.

**********************************************************************



-------------------------------------------------------
SF.Net email is Sponsored by the Better Software Conference & EXPO
September 19-22, 2005 * San Francisco, CA * Development Lifecycle Practices
Agile & Plan-Driven Development * Managing Projects & Teams * Testing & QA
Security * Process Improvement & Measurement * http://www.sqe.com/bsce5sf
_______________________________________________
Bluez-devel mailing list
Bluez-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bluez-devel

Re: [Bluez-devel] sbc decoder unrolled

[Brad Midgley]

Victor,

Yeah, the only thing I didn't like about it is adding a bunch of 
computed array index and index modulo operations... I think we end up 
coming out ahead but I didn't test it specifically.

I could also double the size of sbc_proto_x_x0 and then I wouldn't have 
to worry about the modulo ops wrapping around our indexing into it. That 
will hurt any kind of caching of the array however.

Brad

Victor Shcherbatyuk wrote:
> Brad,
> 
> I'll check if I can do the same for the encoder, getting rid of that
> array shifting might speed up the stuff (well, it will probably add some
> array index operations which might make things worse, but we will see).
> 
> Regards,
>     Victor.
> 
> -----Original Message-----
> From: bluez-devel-admin@lists.sourceforge.net
> [mailto:bluez-devel-admin@lists.sourceforge.net] On Behalf Of Brad
> Midgley
> Sent: Friday, September 09, 2005 7:37 AM
> To: BlueZ Mailing List
> Subject: [Bluez-devel] sbc decoder unrolled
> 
> Hey
> 
> woohoo... I worked over the decoder a lot more and finally unrolled &
> committed it. It still uses floating point for now.
> 
> I was very proud of the fact that I found a way to rotate which
> sbc_proto_x_x0 value we choose rather than shifting matrixed values
> around in every loop. It's even more clear that the implementation they
> illustrate in the spec is meant to make the algorithm clear but not be
> an efficient way to do it.
> 
> I don't know how the instruction cache size in arm compares to x86. I
> haven't checked to see yet if unrolling is as big a win on xscale. fwiw,
> it cut x86 cpu use by about 50% over the looped code.
> 
> I'll look at fixed point next.
> 
> Brad
> 
> 
> -------------------------------------------------------
> SF.Net email is Sponsored by the Better Software Conference & EXPO
> September 19-22, 2005 * San Francisco, CA * Development Lifecycle
> Practices Agile & Plan-Driven Development * Managing Projects & Teams *
> Testing & QA Security * Process Improvement & Measurement *
> http://www.sqe.com/bsce5sf
> _______________________________________________
> Bluez-devel mailing list
> Bluez-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bluez-devel
> 
> 
> This e-mail message contains information which is confidential and may be privileged. It is intended for use by the addressee only. If you are not the intended addressee, we request that you notify the sender immediately and delete or destroy this e-mail message and any attachment(s), without copying, saving, forwarding, disclosing or using its contents in any other way. TomTom N.V., TomTom International BV or any other company belonging to the TomTom group of companies will not be liable for damage relating to the communication by e-mail of data, documents or any other information.
> 
> 
> -------------------------------------------------------
> SF.Net email is Sponsored by the Better Software Conference & EXPO
> September 19-22, 2005 * San Francisco, CA * Development Lifecycle Practices
> Agile & Plan-Driven Development * Managing Projects & Teams * Testing & QA
> Security * Process Improvement & Measurement * http://www.sqe.com/bsce5sf
> _______________________________________________
> Bluez-devel mailing list
> Bluez-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bluez-devel


-------------------------------------------------------
SF.Net email is Sponsored by the Better Software Conference & EXPO
September 19-22, 2005 * San Francisco, CA * Development Lifecycle Practices
Agile & Plan-Driven Development * Managing Projects & Teams * Testing & QA
Security * Process Improvement & Measurement * http://www.sqe.com/bsce5sf
_______________________________________________
Bluez-devel mailing list
Bluez-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bluez-devel

RE: [Bluez-devel] sbc decoder unrolled

[Victor Shcherbatyuk]

Brad,

I think I know another way of getting rid of shifting for the sample
history array (X[] in case of encoder). If I use double sized array (160
elements instead of 80), copy incoming data twice (to both halfs of the
array) and passing a modulo 80 (40 for 4 subbands) index (increased by
8(4) each of the runs) to _sbc_analyse8(4)(), I will eliminate data
shifting at price that I have to copy incoming data twice. So for 8
subbands instead of 72 + 8 mem copies I will have 8+8 mem copies... This
would not require any smart index calculations.

Sorry, just an idea, it might be applicable only to the encoder, do not
have access/time to the code right know, will implement it when I can
(I'm going on vacation for a week)...

Regards,
    Victor.=20

-----Original Message-----
From: bluez-devel-admin@lists.sourceforge.net
[mailto:bluez-devel-admin@lists.sourceforge.net] On Behalf Of Brad
Midgley
Sent: Friday, September 09, 2005 15:16 PM
To: bluez-devel@lists.sourceforge.net
Subject: Re: [Bluez-devel] sbc decoder unrolled

Victor,

Yeah, the only thing I didn't like about it is adding a bunch of
computed array index and index modulo operations... I think we end up
coming out ahead but I didn't test it specifically.

I could also double the size of sbc_proto_x_x0 and then I wouldn't have
to worry about the modulo ops wrapping around our indexing into it. That
will hurt any kind of caching of the array however.

Brad

Victor Shcherbatyuk wrote:
> Brad,
>=20
> I'll check if I can do the same for the encoder, getting rid of that=20
> array shifting might speed up the stuff (well, it will probably add=20
> some array index operations which might make things worse, but we will
see).
>=20
> Regards,
>     Victor.
>=20
> -----Original Message-----
> From: bluez-devel-admin@lists.sourceforge.net
> [mailto:bluez-devel-admin@lists.sourceforge.net] On Behalf Of Brad=20
> Midgley
> Sent: Friday, September 09, 2005 7:37 AM
> To: BlueZ Mailing List
> Subject: [Bluez-devel] sbc decoder unrolled
>=20
> Hey
>=20
> woohoo... I worked over the decoder a lot more and finally unrolled &=20
> committed it. It still uses floating point for now.
>=20
> I was very proud of the fact that I found a way to rotate which=20
> sbc_proto_x_x0 value we choose rather than shifting matrixed values=20
> around in every loop. It's even more clear that the implementation=20
> they illustrate in the spec is meant to make the algorithm clear but=20
> not be an efficient way to do it.
>=20
> I don't know how the instruction cache size in arm compares to x86. I=20
> haven't checked to see yet if unrolling is as big a win on xscale.=20
> fwiw, it cut x86 cpu use by about 50% over the looped code.
>=20
> I'll look at fixed point next.
>=20
> Brad
>=20
>=20
> -------------------------------------------------------
> SF.Net email is Sponsored by the Better Software Conference & EXPO=20
> September 19-22, 2005 * San Francisco, CA * Development Lifecycle=20
> Practices Agile & Plan-Driven Development * Managing Projects & Teams=20
> * Testing & QA Security * Process Improvement & Measurement *=20
> http://www.sqe.com/bsce5sf=20
> _______________________________________________
> Bluez-devel mailing list
> Bluez-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bluez-devel
>=20
>=20
> This e-mail message contains information which is confidential and may
be privileged. It is intended for use by the addressee only. If you are
not the intended addressee, we request that you notify the sender
immediately and delete or destroy this e-mail message and any
attachment(s), without copying, saving, forwarding, disclosing or using
its contents in any other way. TomTom N.V., TomTom International BV or
any other company belonging to the TomTom group of companies will not be
liable for damage relating to the communication by e-mail of data,
documents or any other information.
>=20
>=20
> -------------------------------------------------------
> SF.Net email is Sponsored by the Better Software Conference & EXPO=20
> September 19-22, 2005 * San Francisco, CA * Development Lifecycle=20
> Practices Agile & Plan-Driven Development * Managing Projects & Teams=20
> * Testing & QA Security * Process Improvement & Measurement *=20
> http://www.sqe.com/bsce5sf=20
> _______________________________________________
> Bluez-devel mailing list
> Bluez-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bluez-devel


-------------------------------------------------------
SF.Net email is Sponsored by the Better Software Conference & EXPO
September 19-22, 2005 * San Francisco, CA * Development Lifecycle
Practices Agile & Plan-Driven Development * Managing Projects & Teams *
Testing & QA Security * Process Improvement & Measurement *
http://www.sqe.com/bsce5sf
_______________________________________________
Bluez-devel mailing list
Bluez-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bluez-devel


This e-mail message contains information which is confidential and may be=
 privileged. It is intended for use by the addressee only. If you are not=
 the intended addressee, we request that you notify the sender immediatel=
y and delete or destroy this e-mail message and any attachment(s), withou=
t copying, saving, forwarding, disclosing or using its contents in any ot=
her way. TomTom N.V., TomTom International BV or any other company belong=
ing to the TomTom group of companies will not be liable for damage relati=
ng to the communication by e-mail of data, documents or any other informa=
tion.


-------------------------------------------------------
SF.Net email is Sponsored by the Better Software Conference & EXPO
September 19-22, 2005 * San Francisco, CA * Development Lifecycle Practices
Agile & Plan-Driven Development * Managing Projects & Teams * Testing & QA
Security * Process Improvement & Measurement * http://www.sqe.com/bsce5sf
_______________________________________________
Bluez-devel mailing list
Bluez-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bluez-devel

Re: [Bluez-devel] sbc decoder unrolled

[Brad Midgley]

Steven,

> threshold. (For qualification, they talk about the decoder having a K
> value which needs to be greater than 14).

I had given up on regression tests for accuracy and performance because 
I didn't know about K values and I figured x86 performance might 
actually go down for fixed point (Victor confirmed this)

Google isn't helping me find much about K value this morning but I would 
like to put a regression test in the build if we find something...

> As well as measuring K, you should also listen to the outputs -
> otherwise you may have a bug that sounds bad but somehow manages to
> pass the K test.

Yes... the only thing worse than listening to the reference streams for 
the thousandth time is listening to the reference streams again with 
some new distortion introduced. I ended up encoding some music snipets 
for testing that I (used to) like to listen to :)

thanks for the input

Brad


-------------------------------------------------------
SF.Net email is Sponsored by the Better Software Conference & EXPO
September 19-22, 2005 * San Francisco, CA * Development Lifecycle Practices
Agile & Plan-Driven Development * Managing Projects & Teams * Testing & QA
Security * Process Improvement & Measurement * http://www.sqe.com/bsce5sf
_______________________________________________
Bluez-devel mailing list
Bluez-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bluez-devel

Re: [Bluez-devel] sbc decoder unrolled

[Brad Midgley]

Steven

>   output of reference encoder + your decoder (spec requires K > 14)
>   output of your encoder + reference decoder
>   output of your encoder + your decoder

There is a little gotcha here in that we only have a windows binary for 
a reference encoder/decoder. I haven't tried to build our stuff in 
cygwin or windows dev tools and there are probably things to fix...

Brad


-------------------------------------------------------
SF.Net email is Sponsored by the Better Software Conference & EXPO
September 19-22, 2005 * San Francisco, CA * Development Lifecycle Practices
Agile & Plan-Driven Development * Managing Projects & Teams * Testing & QA
Security * Process Improvement & Measurement * http://www.sqe.com/bsce5sf
_______________________________________________
Bluez-devel mailing list
Bluez-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bluez-devel

RE: [Bluez-devel] sbc decoder unrolled

[Victor Shcherbatyuk]

[-- Attachment #1: Type: text/plain, Size: 1458 bytes --]

Brad,

But why is it a problem? The result of encoding/decoding is save to a file - we compare files... So we run reference encoder under windows (or using wine under linux) and then run our stuff under linux, and compare the results obtained using windows reference ebcoder/decoder?

Regards,
     Victor.


-----Original Message-----
From: bluez-devel-admin@lists.sourceforge.net on behalf of Brad Midgley
Sent: Fri 9/9/2005 7:59 PM
To: bluez-devel@lists.sourceforge.net
Subject: Re: [Bluez-devel] sbc decoder unrolled
 
Steven

>   output of reference encoder + your decoder (spec requires K > 14)
>   output of your encoder + reference decoder
>   output of your encoder + your decoder

There is a little gotcha here in that we only have a windows binary for 
a reference encoder/decoder. I haven't tried to build our stuff in 
cygwin or windows dev tools and there are probably things to fix...

Brad


-------------------------------------------------------
SF.Net email is Sponsored by the Better Software Conference & EXPO
September 19-22, 2005 * San Francisco, CA * Development Lifecycle Practices
Agile & Plan-Driven Development * Managing Projects & Teams * Testing & QA
Security * Process Improvement & Measurement * http://www.sqe.com/bsce5sf
_______________________________________________
Bluez-devel mailing list
Bluez-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bluez-devel


[-- Attachment #2: winmail.dat --]
[-- Type: application/ms-tnef, Size: 3163 bytes --]

Re: [Bluez-devel] sbc decoder unrolled

[Brad Midgley]

Victor,

I was hoping to have regression tests as a regular makefile target... 
it's just more of a pain when it requires shipping stuff around.

However, if we are willing to assume that our floating point 
implementations are correct enough to be our own golden standard, then 
it is pretty straightforward to make a special target that builds both 
and compares them.

Brad

Victor Shcherbatyuk wrote:
> Brad,
> 
> But why is it a problem? The result of encoding/decoding is save to a file - we compare files... So we run reference encoder under windows (or using wine under linux) and then run our stuff under linux, and compare the results obtained using windows reference ebcoder/decoder?
> 
> Regards,
>      Victor.
> 
> 
> -----Original Message-----
> From: bluez-devel-admin@lists.sourceforge.net on behalf of Brad Midgley
> Sent: Fri 9/9/2005 7:59 PM
> To: bluez-devel@lists.sourceforge.net
> Subject: Re: [Bluez-devel] sbc decoder unrolled
>  
> Steven
> 
> 
>>  output of reference encoder + your decoder (spec requires K > 14)
>>  output of your encoder + reference decoder
>>  output of your encoder + your decoder
> 
> 
> There is a little gotcha here in that we only have a windows binary for 
> a reference encoder/decoder. I haven't tried to build our stuff in 
> cygwin or windows dev tools and there are probably things to fix...
> 
> Brad
> 
> 
> -------------------------------------------------------
> SF.Net email is Sponsored by the Better Software Conference & EXPO
> September 19-22, 2005 * San Francisco, CA * Development Lifecycle Practices
> Agile & Plan-Driven Development * Managing Projects & Teams * Testing & QA
> Security * Process Improvement & Measurement * http://www.sqe.com/bsce5sf
> _______________________________________________
> Bluez-devel mailing list
> Bluez-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bluez-devel
> 


-------------------------------------------------------
SF.Net email is Sponsored by the Better Software Conference & EXPO
September 19-22, 2005 * San Francisco, CA * Development Lifecycle Practices
Agile & Plan-Driven Development * Managing Projects & Teams * Testing & QA
Security * Process Improvement & Measurement * http://www.sqe.com/bsce5sf
_______________________________________________
Bluez-devel mailing list
Bluez-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bluez-devel