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

Groups > comp.lang.c > #14159

Re: Shifting bits

Show all headers | View raw

Lauri Alanko <la@iki.fi> writes:

> In article <slrnjdddj9.l6p.usenet-nospam@guild.seebs.net>,
> Seebs  <usenet-nospam@seebs.net> wrote:
>> You propose to create a "division library".  What, exactly, would your
>> division library do that's better than what the compilers do?
>
> There is actually one division optimization case where compilers cannot
> really help and a support library would be useful.
>
> Now, compilers can well optimize a general division where run-time
> operands are arbitrary, either with a dedicated hardware division
> instruction or a subroutine.
>
> Compilers can also optimize a division with a constant into a shift,
> or a multiplication with a reciprocal, or whatever works best on that
> architecture for that particular divisor.
>
> But there's a middle case, where the divisor is not constant, but
> doesn't change very often. For instance, a hash table needs to do a
> modulo operation on every lookup, but the divisor remains the same
> until the table is resized. In such a situation, it would be nice to
> have some way of pre-calculating a division operation for a fixed
> divisor so that it could be performed faster than the the wholly
> general division. In practice this would mean finding the reciprocal
> using the same algorithm the compiler uses for constants.

Maybe it's just the myopia of my custom-hardware-centric experience, but
I don't see cases where that works; what kind of hash function intended
for software-only implementation uses a division but not a remainder?

Assuming it does work (and I'm far enough out of my area that it
wouldn't surprise me), I still don't think the library approach is all
that useful for general division. The library has no knowledge that the
compiler wouldn't, so the programmer needs to provide a priori knowledge
to allow the optimization. You end up with two implementations of the
division operation, and whether the implementations of each are hidden
away in a library or not, the programmer is still coding an explicit
choice between them at the point of use.

-- 
Lowell Gilbert, embedded/networking software engineer
	 http://be-well.ilk.org/~lowell/

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

Thread

Shifting bits arnuld <sunrise@invalid.address> - 2011-11-29 05:02 +0000
  Re: Shifting bits Ian Collins <ian-news@hotmail.com> - 2011-11-29 18:20 +1300
    Re: Shifting bits Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-11-29 17:39 +0000
      Re: Shifting bits arnuld <sunrise@invalid.address> - 2011-11-30 05:53 +0000
        Re: Shifting bits James Kuyper <jameskuyper@verizon.net> - 2011-11-30 06:57 -0500
        Re: Shifting bits Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-11-30 18:31 +0200
          Re: Shifting bits Ralf Damaschke <rwspam@gmx.de> - 2011-12-01 14:41 +0000
            Re: Shifting bits lawrence.jones@siemens.com - 2011-12-01 13:58 -0500
        Re: Shifting bits Stanley Rice <heconghui@gmail.com> - 2011-11-30 18:11 -0800
          Re: Shifting bits Nick Keighley <nick_keighley_nospam@hotmail.com> - 2011-12-01 02:21 -0800
  Re: Shifting bits Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-11-29 03:03 -0800
  Re: Shifting bits "BartC" <bc@freeuk.com> - 2011-11-29 12:04 +0000
    Re: Shifting bits 88888 Dihedral <dihedral88888@googlemail.com> - 2011-11-29 05:44 -0800
    Re: Shifting bits arnuld <sunrise@invalid.address> - 2011-11-30 05:58 +0000
  Re: Shifting bits gwowen <gwowen@gmail.com> - 2011-11-29 08:21 -0800
  Re: Shifting bits DDD <1983ddd@gmail.com> - 2011-11-29 20:42 -0800
    Re: Shifting bits James Kuyper <jameskuyper@verizon.net> - 2011-11-30 00:11 -0500
      Re: Shifting bits Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-11-30 18:23 +0200
        Re: Shifting bits Nick Keighley <nick_keighley_nospam@hotmail.com> - 2011-12-01 02:23 -0800
  Re: Shifting bits 88888 Dihedral <dihedral88888@googlemail.com> - 2011-11-30 05:35 -0800
    Re: Shifting bits Seebs <usenet-nospam@seebs.net> - 2011-11-30 18:43 +0000
      Re: Shifting bits 88888 Dihedral <dihedral88888@googlemail.com> - 2011-11-30 13:33 -0800
        Re: Shifting bits Seebs <usenet-nospam@seebs.net> - 2011-11-30 21:41 +0000
          Re: Shifting bits 88888 Dihedral <dihedral88888@googlemail.com> - 2011-11-30 14:40 -0800
            Re: Shifting bits Seebs <usenet-nospam@seebs.net> - 2011-11-30 22:36 +0000
              Re: Shifting bits Lauri Alanko <la@iki.fi> - 2011-12-01 02:02 +0000
                Re: Shifting bits Lowell Gilbert <lgusenet@be-well.ilk.org> - 2011-12-01 09:30 -0500
              Re: Shifting bits Kaz Kylheku <kaz@kylheku.com> - 2011-12-01 02:50 +0000
                Re: Shifting bits Lowell Gilbert <lgusenet@be-well.ilk.org> - 2011-12-01 09:00 -0500
      Re: Shifting bits Robert Wessel <robertwessel2@yahoo.com> - 2011-11-30 17:09 -0600
    Re: Shifting bits Stanley Rice <heconghui@gmail.com> - 2011-11-30 18:13 -0800
      Re: Shifting bits Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2011-11-30 19:44 -0700
      Re: Shifting bits Keith Thompson <kst-u@mib.org> - 2011-11-30 19:20 -0800
      Re: Shifting bits Seebs <usenet-nospam@seebs.net> - 2011-12-01 20:08 +0000
      Re: Shifting bits Kaz Kylheku <kaz@kylheku.com> - 2011-12-01 21:34 +0000
  Re: Shifting bits gordonb.slo24@burditt.org (Gordon Burditt) - 2011-12-01 01:24 -0600

csiph-web