How to replace /(division) operator

Discussion in 'C Programming' started by spl, Apr 25, 2008.

  1. spl

    spl Guest

    To increase the performance, how to change the / operator with bitwise
    operators?
    for ex: 25/5, 225/25 or 25/3 or any division, but I am not bothered
    of any remainder.
     
    spl, Apr 25, 2008
    #1
    1. Advertising

  2. spl

    jacob navia Guest

    spl wrote:
    > To increase the performance, how to change the / operator with bitwise
    > operators?
    > for ex: 25/5, 225/25 or 25/3 or any division, but I am not bothered
    > of any remainder.


    This is not meaningful if you do not say which CPU
    are you using. Division is not that expensive anymore,
    and the extra code for implementing division with bitwise
    operators could very well be MUCH slower.

    The lcc-win compiler will replace certain kinds of division ( divisions
    by an integer constant) with 3-4 instructions with shifts and adds. This
    is only possible when the divisor is known at compile time.



    --
    jacob navia
    jacob at jacob point remcomp point fr
    logiciels/informatique
    http://www.cs.virginia.edu/~lcc-win32
     
    jacob navia, Apr 25, 2008
    #2
    1. Advertising

  3. spl

    spl Guest

    I use normal Microsoft visual C++ compiler only. Due to lots of more
    frequency in accessing / operator, I feel to change it with bitwise
    operator, as it is always faster then / operator. So, If you know
    bitwise manipulation, please suggest me!!
     
    spl, Apr 25, 2008
    #3
  4. spl

    Chris Dollin Guest

    spl wrote:

    > I use normal Microsoft visual C++ compiler only. Due to lots of more
    > frequency in accessing / operator, I feel to change it with bitwise
    > operator, as it is always faster then / operator.


    Does your application have an actual, measured, performance problem
    that you've tracked down to your use of `/`?

    Sure, individual bitwise operations are often faster than individual
    `/` operations. That's because they do simpler -- different -- things.
    To replace your `/`s with bitwise ops, you'll have to do /multiple/,
    /dependent/ bitwise ops, so it's not longer obvious that this is
    faster.

    --
    "Your world, Colonel, and I wish you the best of it!" /Witch World/

    Hewlett-Packard Limited registered office: Cain Road, Bracknell,
    registered no: 690597 England Berks RG12 1HN
     
    Chris Dollin, Apr 25, 2008
    #4
  5. spl

    spl Guest

    On Apr 25, 2:03 pm, Chris Dollin <> wrote:
    > spl wrote:
    > > I use normal Microsoft visual C++ compiler only. Due to lots of more
    > > frequency in accessing / operator, I feel to change it with bitwise
    > > operator, as it is always faster then / operator.

    >
    > Does your application have an actual, measured, performance problem
    > that you've tracked down to your use of `/`?


    YES. I have.
     
    spl, Apr 25, 2008
    #5
  6. spl

    Bartc Guest

    "spl" <> wrote in message
    news:...
    >I use normal Microsoft visual C++ compiler only. Due to lots of more
    > frequency in accessing / operator, I feel to change it with bitwise
    > operator, as it is always faster then / operator. So, If you know
    > bitwise manipulation, please suggest me!!


    Do you know what sort of numbers are being operated on?

    Are the numbers you divide by, constants? If not things are more difficult.

    Dividing by a power of 2 can sometimes be replaced by a shift, if you know
    the number. (If not, but is a power of 2, you can keep track of the shift
    count needed.) However, if it's something obvious, the compiler will already
    have done it!

    How much runtime is given over to division anyway? On what processor (as
    they are all different)?

    Can you post some test code that demonstrates the problem you have?

    Sometimes you can rearrange the code to reduce or eliminate division.

    --
    Bart
     
    Bartc, Apr 25, 2008
    #6
  7. spl

    Chris Dollin Guest

    spl wrote:

    > On Apr 25, 2:03 pm, Chris Dollin <> wrote:
    >> spl wrote:
    >> > I use normal Microsoft visual C++ compiler only. Due to lots of more
    >> > frequency in accessing / operator, I feel to change it with bitwise
    >> > operator, as it is always faster then / operator.

    >>
    >> Does your application have an actual, measured, performance problem
    >> that you've tracked down to your use of `/`?

    >
    > YES. I have.


    Then you can tell us the numbers and the context and the code
    that is slow, and get advice suited to your actual problem
    rather than speculation into the vacuum.

    (And note that you'll get /C/ advice; if you have a C++ program,
    it's possible that there will be better C++-oriented answers
    in A Different Group.)

    --
    "It was the first really clever thing the King had /Alice in Wonderland/
    said that day."

    Hewlett-Packard Limited registered office: Cain Road, Bracknell,
    registered no: 690597 England Berks RG12 1HN
     
    Chris Dollin, Apr 25, 2008
    #7
  8. spl wrote:
    > I use normal Microsoft visual C++ compiler only. Due to lots of more
    > frequency in accessing / operator, I feel to change it with bitwise
    > operator, as it is always faster then / operator. So, If you know
    > bitwise manipulation, please suggest me!!


    You are probably confused about what language you are using. The C
    programing language (the one discussed in the newsgroup you posted to,
    <news:comp.lang.c>) does not allow you to redefine the meaning of
    operators like '/'.

    There are other puzzling things about your post. If you actually knew
    the "bitwise operator, as it is always faster than / operator", then you
    would already have the implementation you want. In that case, you would
    have no need of anyone to "please suggest me!!". And if your claim were
    in any sense true, why would you think that the Microsoft compiler
    developers did not already use this supposed "always faster" approach
    for their implementation of the '/' operator?

    I fear that you are very confused, or erroneously parroting someone
    else, or simply a troll.
     
    Martin Ambuhl, Apr 25, 2008
    #8
  9. spl

    spl Guest

    Sorry for the delay in getting back to your questions, Actually
    changing the division operator to bitwise operators is suggested by my
    tech lead. As she done so many such improvement by doing this and she
    is having enough evidence for the same. She suggested me to do the
    same in my current project too. Actually I want to divide some big
    number with constant number, say 1024 always. Please give me your
    suggestion please.
     
    spl, Apr 28, 2008
    #9
  10. spl

    Bartc Guest

    "spl" <> wrote in message
    news:...
    > Sorry for the delay in getting back to your questions, Actually
    > changing the division operator to bitwise operators is suggested by my
    > tech lead. As she done so many such improvement by doing this and she
    > is having enough evidence for the same. She suggested me to do the
    > same in my current project too. Actually I want to divide some big
    > number with constant number, say 1024 always. Please give me your
    > suggestion please.


    My suggestion is to just divide by 1024.

    Your compiler will use the most appropriate coding, you probably don't even
    have to tell it to optimise.

    Only if your compiler is so basic that you might try using (A>>10) instead
    of A/1024, if A is an appropriate type like int, followed by a comment as to
    why you are doing this.

    --
    Bartc
     
    Bartc, Apr 28, 2008
    #10
  11. spl

    spl Guest

    Thanks Bartc & Eric. Your suggestions are very useful. By the way all
    my variables are unsigned int only. So right shift gives me exact
    value.
     
    spl, Apr 28, 2008
    #11
  12. spl

    Guest

    On 28 Apr., 14:15, Eric Sosman <> wrote:
    > Bartc wrote:
    > > "spl" <> wrote in message
    > >news:...
    > >> Sorry for the delay in getting back to your questions, Actually
    > >> changing the division operator to bitwise operators is suggested by my
    > >> tech lead. As she done so many such improvement by doing this and she
    > >> is having enough evidence for the same. She suggested me to do the
    > >> same in my current project too. Actually I want to divide some big
    > >> number with constant number, say 1024 always. Please give me your
    > >> suggestion please.

    >
    > > My suggestion is to just divide by 1024.

    >
    > > Your compiler will use the most appropriate coding, you probably don't even
    > > have to tell it to optimise.

    >
    > > Only if your compiler is so basic that you might try using (A>>10) instead
    > > of A/1024, if A is an appropriate type like int, followed by a comment as to
    > > why you are doing this.

    >
    > Pay close attention to that "appropriate type" part, and
    > view "like int" with caution. The problem is that the result
    > of right-shifting a negative number is implementation-defined,
    > and is usually not the same as the result of dividing by two.
    > For example, on the two's complement machines that are all
    > but universal nowadays the representation of -1 is a string
    > of 1-bits. Shift the string one place to the right and you
    > may get another string of 1-bits ("arithmetic shift") or a
    > single 0-bit followed by 1-bits ("logical shift"). The first
    > thus gives -1 again, while the second gives a large positive
    > result -- but neither gives the correct result -1 / 2 == 0.
    >
    > So: "appropriate type" means either an *unsigned* integer
    > or a signed integer that you happen to know is non-negative.


    Agreed.
    There can be even more problems with negative numbers.
    IMHO the definition of the division in C89 allows also
    -1 / 2 == -1. Although I did not find a C compiler which
    does this, it is theoretically possible since in C89 the
    division is defined as follows:

    The binary / operator yields the quotient, and the % operator
    the remainder, of the first operand by the second; if the
    second operand is 0, the result is undefined. Otherwise, it
    is always true that (a/b)*b + a%b is equal to a. If both
    operands are non-negative, the remainder is non-negative and
    smaller than the divisor; if not it is guaranteed only that
    the absolute value of the remainder is smaller than the
    absolute value of the divisor.

    As said before this definition allows that the integer
    division can be rounded towards minus infinite.
    Note that when -1 / 2 == -1 at the same time -1 % 2 == 1

    IMHO this definition was chosen to allow integer operations
    with one machine instruction.

    Greetings Thomas Mertes

    Seed7 Homepage: http://seed7.sourceforge.net
    Seed7 - The extensible programming language: User defined statements
    and operators, abstract data types, templates without special
    syntax, OO with interfaces and multiple dispatch, statically typed,
    interpreted or compiled, portable, runs under linux/unix/windows.
     
    , Apr 28, 2008
    #12
  13. On Apr 28, 10:13 am, spl <> wrote:
    > Sorry for the delay in getting back to your questions, Actually
    > changing the division operator to bitwise operators is suggested by my
    > tech lead. As she done so many such improvement by doing this and she
    > is having enough evidence for the same. She suggested me to do the
    > same in my current project too. Actually I want to divide some big
    > number with constant number, say 1024 always. Please give me your
    > suggestion please.


    Write two functions

    unsigned int f1 (unsigned int x) { return x / 1024; }
    unsigned int f2 (unsigned int x) { return x >> 10; }

    Find a way to make the compiler show the assembler code that it
    generates and compare. If you get different code, tell us which
    compiler you are using so we can all avoid it. I can't actually
    remember any C compiler that wouldn't produce optimal code for the
    division, and that is going back more than 20 years.
     
    christian.bau, May 3, 2008
    #13
  14. On May 3, 12:59 pm, "christian.bau" <>
    wrote:
    > On Apr 28, 10:13 am, spl <> wrote:
    >
    > > Sorry for the delay in getting back to your questions, Actually
    > > changing the division operator to bitwise operators is suggested by my
    > > tech lead. As she done so many such improvement by doing this and she
    > > is having enough evidence for the same. She suggested me to do the
    > > same in my current project too. Actually I want to divide some big
    > > number with constant number, say 1024 always. Please give me your
    > > suggestion please.

    >
    > Write two functions
    >
    >   unsigned int f1 (unsigned int x) { return x / 1024; }
    >   unsigned int f2 (unsigned int x) { return x >> 10; }
    >
    > Find a way to make the compiler show the assembler code that it
    > generates and compare. If you get different code, tell us which
    > compiler you are using so we can all avoid it. I can't actually
    > remember any C compiler that wouldn't produce optimal code for the
    > division, and that is going back more than 20 years.


    Oh, I just noticed you mentioned using a reasonably modern Microsoft
    compiler.

    In that case, you should also check what code is produced for

    unsigned int f3 (unsigned int x) { return x / 1000; }

    and ask your lead to explain the code that is generated. Have fun.
     
    christian.bau, May 3, 2008
    #14
  15. On Apr 25, 1:51 pm, spl <> wrote:
    > I use normal Microsoft visual C++ compiler only. Due to lots of more
    > frequency in accessing / operator, I feel to change it with bitwise
    > operator, as it is always faster then / operator. So, If you know
    > bitwise manipulation, please suggest me!!



    If you can do it faster on your own, I'll take out a loan and buy you
    a Porsche.

    As others have said, a bitwise instruction might take less CPU cycles
    on your platform than a division instruction, but I can guarantee that
    the amount of bitwise instruction you use will result in the division
    instruction being faster.

    In fact, it it were possible to get better performance using your own
    bitwise instructions, then I think a lot of people would be ringing up
    the CPU manufacturer to ask why the division instruction isn't done
    efficiently.
     
    Tomás Ó hÉilidhe, May 3, 2008
    #15
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Brian Blais
    Replies:
    1
    Views:
    395
    Bruno Desthuilliers
    Jun 27, 2006
  2. Sri

    Implementing the division operator

    Sri, May 1, 2006, in forum: C Programming
    Replies:
    13
    Views:
    4,144
  3. Replies:
    94
    Views:
    4,570
    ¬a\\/b
    Feb 9, 2007
  4. Replies:
    1
    Views:
    991
    Alf P. Steinbach
    Jan 19, 2007
  5. Michael Neumann
    Replies:
    29
    Views:
    388
    Michael Neumann
    Jun 11, 2004
Loading...

Share This Page