Contains.kt

package qwwdfsad

import org.openjdk.jmh.annotations.*
import org.openjdk.jmh.infra.Blackhole
import java.util.concurrent.*
import kotlin.random.*

@Warmup(iterations = 3, time = 1)
@Measurement(iterations = 5, time = 1)
@Fork(value = 1)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@State(Scope.Benchmark)
open class XodusLikeContainsBenchnmark {

    companion object {

        val rigged = Random(239)

        val dataset = buildList {
            repeat(30_000) {
                add("build-$it")
            }

            val alphabet = (('0'..'9') + ('a'..'z') + ('A'..'Z')).toList()
            repeat(30_000) {
                add(buildString { repeat(Random.nextInt(5, 25)) { append(alphabet.random()) } })
            }

            repeat(30_000) {
                add("tag-$it")
            }
        }.shuffled()

        @JvmStatic
        fun main(args: Array<String>) {
            val needle = "TaG-12"
            val s1 = mutableSetOf<String>()
            val s2 = mutableSetOf<String>()
            for (s in ContainsIterator(needle, true)) {
                s1.add(s)
            }
            for (s in OptimizedContainsIterator(needle, true)) {
                s2.add(s)
            }
            println(s1 == s2)
        }
    }

    class ContainsIterator(private val value: String, private val ignoreCase: Boolean) : Iterator<String> {
        private var idx = 0
        private var next: String? = null

        override fun hasNext(): Boolean {
            while (idx < dataset.size) {
                val next = dataset[idx++]
                if (next.contains(value, ignoreCase)) {
                    this.next = next
                    return true
                }
            }
            return false
        }

        override fun next(): String {
            return next!!
        }
    }

    class OptimizedContainsIterator(value: String, private val ignoreCase: Boolean) : Iterator<String> {
        private var idx = 0
        private var next: String? = null

        private val value = if (ignoreCase) value.lowercase() else value


        override fun hasNext(): Boolean {
            while (idx < dataset.size) {
                val next = dataset[idx++]
                if (containsValue(next)) {
                    this.next = next
                    return true
                }
            }
            return false
        }

        private fun containsValue(entry: String): Boolean {
            if (!ignoreCase) return entry.contains(value)

            val searchEnd: Int = entry.length - value.length + 1
            if (searchEnd < 0) {
                return false
            }
            if (value.length == 0) {
                return true
            }
            outer@ for (i in 0 until searchEnd) {
                for (j in 0 until value.length) {
                    if (entry[i + j].lowercaseChar() != value[j]) {
                        continue@outer
                    }
                }
                return true
            }

            return false
        }

        override fun next(): String {
            return next!!
        }
    }

    @Benchmark
    fun baseline(bh: Blackhole) {
        doRun(bh) {
            ContainsIterator(it, true)
        }
    }

    @Benchmark
    fun baselineCaseSensitive(bh: Blackhole) {
        doRun(bh) {
            ContainsIterator(it, false)
        }
    }

    @Benchmark
    fun optimized(bh: Blackhole) {
        doRun(bh) {
            OptimizedContainsIterator(it, true)
        }
    }

    @Benchmark
    fun optimizedCaseSensitive(bh: Blackhole) {
        doRun(bh) {
            OptimizedContainsIterator(it, false)
        }
    }

    private fun doRun(bh: Blackhole, createIter: (needle: String) -> Iterator<String>) {
        val needle = dataset.random(rigged).apply { substring(0, (length / 2).coerceAtLeast(1)) }
        val iterator = createIter(needle)
        for (element in iterator) {
            bh.consume(element)
        }
    }
}