7 Replies - 13085 Views - Last Post: 03 August 2013 - 06:32 AM

#1 ghqwerty  Icon User is offline

  • if($spareTime > 0){ $this->writeCode(); }
  • member icon

Reputation: 43
  • View blog
  • Posts: 903
  • Joined: 08-August 08

Which way is quicker, Int or Bool

Posted 01 January 2012 - 10:49 AM

Ok so i have a fully working function which i'm just trying to optimize right now.

currently i have the following few lines in my code

 
c = a + b + remainder


Where a and b are < 10 and remainder is an integer of value 0 or 1.

I got to thinking if it would be faster storing remainder as a boolean and then doing

If remainder Then 
c = a + b + 1
else
c = a+b
End If



This is part of my string addition script which adds big number in string format together. It's already ridiculously fast for small numbers and the variation of bool and int makes little visible difference.

However, for 2 numbers with > 300 digits+decimals it seems to run in about a THIRD of the time.
Original runtime ~19ms
with bool 'variation' ~ 6ms

So i'm posting this to see if somebody could explain the huge difference in speed, and also as a pointer to other people who might be in the same situation.

Is This A Good Question/Topic? 0
  • +

Replies To: Which way is quicker, Int or Bool

#2 demausdauth  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 176
  • View blog
  • Posts: 638
  • Joined: 03-February 10

Re: Which way is quicker, Int or Bool

Posted 01 January 2012 - 11:23 AM

If you use an integer and then put that value in a situation where it can/would be converted to a boolean value, then VB can and will implicitly convert it for you. However, this is at the expense of converting the integer to a boolean and then processing the if statement. Whereas if you are outright using a boolean type then there is no need to do the conversion.
Was This Post Helpful? 0
  • +
  • -

#3 birty  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 22-February 12

Re: Which way is quicker, Int or Bool

Posted 22 February 2012 - 03:20 AM

At first, the result seemed counter intuitive because you had added an if branch (which potentially defeats the 'CPU branch prediction' logic increasing CPU stalling in bottleneck routines). However then I noticed from your comment that a and b are strings.
Concatenating strings is notoriously slow in bottleneck routines. Each concatenation (+ operator) in the statement incurs another memory allocation overhead. The speedup is because some of the time, you are now only concatenting two strings, not three. It is interesting that there seems to be a bigger than expected additional overhead from concatenating two long strings to concatenating three strings, implying the performance of subsequent string (+) operations in the same statement gets worse and worse and worse.

It is good practice to use System.IO.StringBuilder when several concatenations are involved in a bottleneck routine, as this allocates a single block of memory (a buffer) 'up front' then is populated with subsequent calls to 'Append'. When finished appending, simply call the ToString method to get a copy of the string you just built. To 'reset' a stringbuilder in a loop, simply set the Length to zero, so you can reuse the same stringbuilder memory buffer again.
Was This Post Helpful? 0
  • +
  • -

#4 lar3ry  Icon User is offline

  • Coding Geezer
  • member icon

Reputation: 310
  • View blog
  • Posts: 1,290
  • Joined: 12-September 12

Re: Which way is quicker, Int or Bool

Posted 08 May 2013 - 07:14 AM

This is part of my string addition script which adds big number in string format together.

Your question reminded me of a machine IBM made, many years ago. The IBM 1620. We used to call it CADET, which stood for Can't Add, Doesn't Even Try.

It could, however, make use of a scheme that was actually a clever table lookup. The table was based at a fixed address, and in order to add, the digits were fetched one at a time, starting with the lowest order ones, in pairs. The digits were stored in the two decimal digit positions after the table's base, and then the table was accessed at the address formed. At that address, was the sum of the two digits, and a flag bit that indicated a carry. The carry was remembered for the next fetch. There's a Wikipedia article on the 1620.

' Example: 94 + 255
      ' Assuming the table resides at address 400
      '   Table address = 445     (two lowest order digits)
      '    at that address we find 9  (no flag)
      '   Table address = 495
      '     at that address we find 4 (with flag)
      '   Table address 402  (no more digits in first number)
      '     at that address we find 2, and remember the carry, so incrment


I have occasionally thought it might be intersting to write this in a modern language.
Was This Post Helpful? 0
  • +
  • -

#5 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 1949
  • View blog
  • Posts: 4,048
  • Joined: 11-December 07

Re: Which way is quicker, Int or Bool

Posted 30 May 2013 - 06:16 AM

What would be really interesting is to run your benchmark with these possibilities too:

c = a + b + remainder
c = a + remainder + b
c = b + remainder + a
c = remainder + a + b
c = remainder + b + a


String addition is O(N) which means adding two small numbers is quick and adding two large numbers is slow.

If you add 1 to 10, that's fast. Adding 1 to 10^300 is slooow.

A reasonable strategy is to look after the cases for large N. Small N will be quick anyway.

This post has been edited by cfoley: 30 May 2013 - 06:16 AM

Was This Post Helpful? 0
  • +
  • -

#6 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2251
  • View blog
  • Posts: 9,435
  • Joined: 29-May 08

Re: Which way is quicker, Int or Bool

Posted 30 May 2013 - 09:57 AM

.Net 4.0+ has a BigInteger library if you add a reference to the namespace System.Numerics.

You use is to implement arbitrary precision number class if you work out away to track the location of the decimal point.


Quote

Adding 1 to 10^300 is slooow.

No if you exit on first no carry.

Adding 1 to (10^300)-1 would be slow as it involves a carry for every digit.

This post has been edited by AdamSpeight2008: 30 May 2013 - 10:06 AM

Was This Post Helpful? 0
  • +
  • -

#7 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 1949
  • View blog
  • Posts: 4,048
  • Joined: 11-December 07

Re: Which way is quicker, Int or Bool

Posted 30 May 2013 - 03:07 PM

His implementation is on Strings. Since Strings are immutable, you have to create a new String and copy 300 characters even if there are no carries.

Slooow ;)
Was This Post Helpful? 0
  • +
  • -

#8 dbasnett  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 109
  • View blog
  • Posts: 603
  • Joined: 01-October 08

Re: Which way is quicker, Int or Bool

Posted 03 August 2013 - 06:32 AM

View Postlar3ry, on 08 May 2013 - 09:14 AM, said:

...Your question reminded me of a machine IBM made, many years ago. The IBM 1620. We used to call it CADET, which stood for Can't Add, Doesn't Even Try.


Insert
160001000000
Release
Start
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1