Quiz: Which Is Faster?

[keirS]

I used to like Erel's quizzes but he doesn't seem to post them anymore. So it thought I post a little problem. Recently I needed to find the length of an integer. Actually I needed to find the length of lots of integers. There are lots of ways to do this.

Cast to a String and get the length:

Sub LengthOfLong1(n As String) As Int

    Return n.Length
   
End Sub

Use some maths:

Sub LengthOfLong2 (n As Long) As Int
    Return Logarithm(n,10)+1
   
   
End Sub

Lots and Lots of If statements:

Sub LengthOfLong3 (n As Long) As Int


    If n < 10000 Then
        If  n < 100  Then
            If n < 10 { Then
                Return 1
             Else
                Return 2
           End If 
         Else 
            If n < 1000  Then
                Return 3
             Else 
                Return 4
            End If 
        End If          
    Else 
        If n < 1000000000000  Then
            If n < 100000000 Then
                If n < 1000000 Then
                    If n < 100000 Then
                        Return 5
                     Else 
                        Return 6
                    End If 
                 Else 
                    If n < 10000000 Then
                        Return 7
                     Else 
                        Return 8
                    End If 
                End If
            Else
                If n < 10000000000 Then
                    If n < 1000000000 Then
                        Return 9
                     Else 
                        Return 10
                   End If
                 Else 
                    If n < 100000000000 Then
                        Return 11
                     Else 
                        Return 12
                    End If
                End If 
            End If 
         Else 
            If n < 10000000000000000 Then
                If n < 100000000000000 Then
                    If n < 10000000000000 Then
                        Return 13
                     Else 
                        Return 14
                    End If 
                Else
                    If n < 1000000000000000 Then
                        Return 15
                    Else 
                        Return 16
                    End If
                End If 
            Else 
                If n < 1000000000000000000 Then
                    If n < 100000000000000000 Then
                        Return 17
                   Else 
                        Return 18
                    End If 
                 Else 
         
                    Return 19
                End If
            End If
       End If
    End If
End Sub

One of these subs is significantly faster. Which one is it? No cheating by running the code!

 

[canalrun]

I am going to guess "if" statements.

I think you can make this a poll somehow. Fun question.

 

[LucaMs]

I think Logarithm

 

[keirS]

Poll added.

 

[Descartex]

Obviously the nested If because they does not trigger any internal "Sub"...

 

[Erel]

Voted for the first option (though not sure at all).

 

[Cableguy]

Voted for the first option (though not sure at all).

Lol

 

[JordiCP]

I would say the 3rd, but no idea

 

[ilan]

I voted for solution 1 because its faster to write down the code (i am not sure if it performs faster but i need to think how to make my code as simple as possible so when i leave it for few month and want to update something so i wont need to buy to much asperin for that)

 

[LucaMs]

I'm surprised that you all do not vote the number 2, as I did, since it is an internal function and it is not a string function, notoriously slow.

I'm surprised also about another thing, but this is another story

 

[Beja]

Voted number 2

 

[keirS]

My test code.

Dim intArray (1000000) As Int
Dim nTime As Long
    Dim result As Int
    For cntr = 0 To (1000000 - 1)
     intArray(cntr) = Rnd(0, 214483647)
    Next
 
 
    nTime = DateTime.Now
    For cntr = 0 To (1000000 - 1)
     LengthOfLong3(intArray(cntr))
    Next
    Label1.Text = "LengthOfLong3: " & ((DateTime.Now - nTime) & "Ms")
 
     
    nTime = DateTime.Now
    For cntr = 0 To (1000000 - 1)
     LengthOfLong2(intArray(cntr))
    Next
    Label2.Text = "LengthOFLong2: " & ((DateTime.Now - nTime) & "Ms")
 
    nTime = DateTime.Now
    For cntr = 0 To (1000000 - 1)
     LengthOfLong1(intArray(cntr))
    Next
    Label3.Text = "LengthOfLong1: " & ((DateTime.Now - nTime) & "Ms")
 

    nTime = DateTime.Now
    For cntr = 0 To (1000000 - 1)
     LengthOfLong1(intArray(cntr))
    Next
    Label4.Text = "LengthOfLong1: " & ((DateTime.Now - nTime) & "Ms")
 
 
    nTime = DateTime.Now
    For cntr = 0 To (1000000 - 1)
     LengthOfLong2(intArray(cntr))
    Next
    Label5.Text = "LengthOfLong2: " & ((DateTime.Now - nTime) & "Ms")
 
    nTime = DateTime.Now
    For cntr = 0 To (1000000 - 1)
     LengthOfLong3(intArray(cntr))
    Next
    Label6.Text = "LengthOfLong3: " & ((DateTime.Now - nTime) & "Ms")

Times in B4J 4.01 running on Windows 7 with an I7 2.6ghz processor with JDK 1.8

So LengthOfLong3 is 5 times faster.

On my Pixel C Tablet B4A 6.3, JDK 1.8 and the target SDK as 19

Massive difference! The If statements are over 20 times faster than the cast to string.

 

[LucaMs]

My test code.

I did a test immediatly after my perfect answer:

I think Logarithm

and, of course, I got your same result:
3 fastest, 1 slowest

This is why...

I'm surprised also about another thing, but this is another story

To me it is surprising (but if it were not so you would not have asked the question )

 

[sorex]

makes sense as core routines are general routines and not focussed on a/the specific task like what you're doing here
so they probably do object type checking, using a count loop etc that cause this overhead.

your code can be even improved especially when you know in what range most of your values will be.

 

[thedesolatesoul]

Nice one. I would have voted for 1.

There is however a small flaw in your benchmarks which favours LengthOfLong3 i.e.
>>> math.log(214483647,10)
8.331394185619123

So you only really execute the faster branches in your code, you never execute the later branches. Maybe.
On visual inspection the depth of nesting seems equal so it may not be an issue?

The reason LengthOfLong3 is coming faster is probably because it can exit earlier on smaller numbers.
On a distrubution of 10M numbers, chances are a half of them are faster and half of them are slower. That said, also depends on the number of conditionals you have.

What I'm more surprised about is the difference between LengthOfLong1 vs LengthOfLong2 on x86 and ARM.
Looks like ARM has dedicated ISA for Logarithm. Or faster FPU.

 

[keirS]

LengthOfLong3 is optimized for small integers of < 9999 so the IF branches are unbalanced towards this. 214483647 is the maximum size of a positive Int in B4X/Java. I couldn't be bothered writing my own RND function that supports Long but the branching goes up to 19 to support the maximum value for a Long which is 9223372036854775807.

 

[LucaMs]

(I should open a new thread - maybe a new quiz)

This may seem more intuitive but not too much.

I wanted to compare speed when using literals vs constants (integers).

Dim Value As String = "Ciao"

For i = 1 To 10000000
    Select Value
        Case "Addio"
        Case "Arrivederci"
        Case "A domani"
        Case "A mai più"
        Case "Ciao"
           ' here I wrote some stuff
    End Select
Next

' Vs
Dim Value As Int = 5

For i = 1 To 10000000
    Select Value
        Case SALUTO_Addio ' <--- Int constant
        Case SALUTO_Arrivederci
        Case SALUTO_A_Domani
        Case SALUTO_A_mai_più
        Case SALUTO_Ciao
           ' here I wrote some stuff
    End Select
Next

It may seem obvious but I thought that the compilation would have prepared each Case statement and then...
Well, my hope was in vain. Times (seconds & ms): literals 9:009 constants: 11:011.
It is not a big difference since the test was made on 10 million cycles but... there is.

So I can conclude by saying... use anyway constants

 

[wonder]

Guys, guys, come on...

Sub NumberOfDigits(n As Long) As Short
    Dim i = 1 As Short, p = 10 As Long
    Do While n / p > 1 : p = p * 10 : i = i + 1 : Loop
    Return i
End Sub

Can anyone test it?

 

[keirS]

Congratulations you have come up with the slowest method......

 

[LucaMs]

Congratulations you have come up with the slowest method......

I have got these results (ms), testing For i = 1 To 100000:
1
264
2
043
3
028

NumberOfDigits
018