Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch > #6670

Re: ffs16

Cross-posted to 2 groups.

Show all headers | View raw

Joe keane wrote:
> In article<qgem69-75r2.ln1@ntp6.tmsw.no>,
> Terje Mathisen<"terje.mathisen at tmsw.no">  wrote:
>> Problem two: The tests have a really funky way to randomize the tests
>> (multiply by 31), which means that the table lookup version will have
>> very close to 100% branch prediction hits for the pattern of switching
>> between the top and low byte.
>
> The big problem is that the distribution is wrong.  I think we want
> values of the *output* to be about equally probable, so the branch is
> taken 50%.  And of course we don't want it to be too predictable.
>
> Of course there's the case where it runs smoothly with some stupid toy
> test program, but goes haywire when it's inside a 'real' program.  Miss
> rate higher than 10% scares me; mispredicted branches are -bad-.
>
> That explains my interest in 'branchless' code.  I don't care if it
> tests worse for a simple case, if it can avoid some bad behavior.

In which case I'll have to repeat my suggestion of using the table-less 
fp version: Same speed (within +/- 15% or so), zero branches.

If you do this a lot then you can very easily pipeline multiple 
conversions and get the throughput to approximate one/cycle.

With a compiler which knows about things like vectorized SSE code, I 
would expect 4 such conversions in parallel:

  ;; Load 4 32-bit ints, converting to float:
  cvtdq2ps xmm0,[four_32_bit_int_inputs]

  ;; shift right 23 bits
  psrld xmm0,23

  ;; Subtract the 127 bias
  psubd xmm0,[four_X_127]

If you can get your compiler to generate approximately this code, then 
you could be faster than scalar Bit Scan opcodes. :-)

Terje
-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

Back to comp.arch | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

ffs16 jgk@panix.com (Joe keane) - 2012-04-22 21:36 +0000
  Re: ffs16 Keith Thompson <kst-u@mib.org> - 2012-04-22 15:23 -0700
  Re: ffs16 Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-04-22 20:37 -0400
    Re: ffs16 Philip Lantz <prl@canterey.us> - 2012-04-24 06:36 -0700
      Re: ffs16 Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-04-24 20:32 -0400
        Re: ffs16 Philip Lantz <prl@canterey.us> - 2012-04-25 00:30 -0700
  Re: ffs16 Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-04-23 16:22 +0200
    Re: ffs16 Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-04-23 21:46 -0400
      Re: ffs16 Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-04-24 14:16 +0200
        Re: ffs16 Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-04-24 20:40 -0400
    Re: ffs16 jgk@panix.com (Joe keane) - 2012-04-24 19:06 +0000
      Re: ffs16 Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-04-25 00:38 +0200
        Re: ffs16 jgk@panix.com (Joe keane) - 2012-04-25 20:08 +0000
          Re: ffs16 "James Van Buskirk" <not_valid@comcast.net> - 2012-04-25 15:06 -0600
            Re: ffs16 "James Van Buskirk" <not_valid@comcast.net> - 2012-04-25 16:30 -0600
        Re: ffs16 jgk@panix.com (Joe keane) - 2012-04-25 21:25 +0000
          Re: ffs16 Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-04-26 01:38 +0200
            Re: ffs16 jgk@panix.com (Joe keane) - 2012-04-26 19:34 +0000
            Re: ffs16 jgk@panix.com (Joe keane) - 2012-04-26 20:41 +0000
              Re: ffs16 Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-04-27 02:47 +0200
  Re: ffs16 MitchAlsup <MitchAlsup@aol.com> - 2012-04-23 13:01 -0700
    Re: ffs16 Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-04-24 03:28 +0200
      Re: ffs16 nmm1@cam.ac.uk - 2012-04-24 09:15 +0100
      Re: ffs16 Chris Gray <cg@GraySage.com> - 2012-04-24 13:37 -0600

csiph-web