kotlin list binarySearch

Question

I was playing with extension functions and tried to do binarySearch function on lists. And I realized that there is an extension function already that is builtin in Kotlin. However, it is very slow: -

public fun <T: Comparable<T>> List<T?>.binarySearch(element: T?, fromIndex: Int = 0, toIndex: Int = size): Int {
     rangeCheck(size, fromIndex, toIndex)

     var low = fromIndex
     var high = toIndex - 1

     while (low <= high) {
         val mid = (low + high).ushr(1) // safe from overflows
         val midVal = get(mid)
         val cmp = compareValues(midVal, element)

         if (cmp < 0)
             low = mid + 1
         else if (cmp > 0)
             high = mid - 1
         else
             return mid // key found
     }
     return -(low + 1)  // key not found
}

I have edited the function and removed the function call (compareValues) and the replacement function is way faster

test_buildin_binary_search         8s35m
test_binary_search           584ms

^based on my test I will attach it down.

the new one: -

fun rangeCheck(size: Int, fromIndex: Int, toIndex: Int) {
    when {
        fromIndex > toIndex -> throw IllegalArgumentException("fromIndex ($fromIndex) is greater than toIndex ($toIndex).")
        fromIndex < 0 -> throw IndexOutOfBoundsException("fromIndex ($fromIndex) is less than zero.")
        toIndex > size -> throw IndexOutOfBoundsException("toIndex ($toIndex) is greater than size ($size).")
    }
}

fun <T : Comparable<T>> binarySearch(list: List<T?>, element: T?, fromIndex: Int = 0, toIndex: Int = list.size): Int {
    rangeCheck(list.size, fromIndex, toIndex)

    var low = fromIndex
    var high = toIndex - 1

    while (low <= high) {
        val mid = (low + high).ushr(1) // safe from overflows
        val midVal = list.get(mid)
        val cmp = element?.compareTo(midVal as T) as Int

        if (cmp < 0)
            low = mid + 1
        else if (cmp > 0)
            high = mid - 1
        else
            return mid // key found
    }
    return -(low + 1)  // key not found
}

It is not an extension function so far. But I believe that the inside function call is the reason of making it slow.

Q1. why compareValues is not an inline function? maybe due to design decisions? where it is not always a good idea to inline it?

Q2. Is there a keyword that gives the programmer the freedom to inline function "f1" for example where f1 is not inline function?

I mean why there is no keyword like "inlineit" and it is used as: -

 fun f1() {
    println("something")
 }

 fun main() {
     inlineit f1() // line 1
     f1() // line 2
 }

Where in this case f1() will be inlined only when we use the keyword inlineit in front of its name, in above code f1() in line 1 is inlined but in line 2 is not.

The junit test: -

class BinarySearchTests() {
    private val max = 10_000_000
    private val times = 10_000_000
    private val largNumbers = (0..max).toList()
    private val r = Random(System.currentTimeMillis())

    @Test
    fun test_binary_search() {
        var found = false

        repeat(times) {
            val item = r.nextInt(max)

            val r = binarySearch(largNumbers, item)

            if (r != null) found = true
        }

        assert(found)
    }


    @Test
    fun test_buildin_binary_search() {
        var found = false

        repeat(times) {
            val item = r.nextInt(max)

            val r = largNumbers.binarySearch(item)

            if (r != -1) found = true
        }

        assert(found)
    }

}

Thank you