Skip to content

Instantly share code, notes, and snippets.

@travisbrown
Created June 26, 2017 18:10
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save travisbrown/09e65c23044551ca9abcdc79dee6319c to your computer and use it in GitHub Desktop.
Save travisbrown/09e65c23044551ca9abcdc79dee6319c to your computer and use it in GitHub Desktop.
def parseLong(input: CharSequence, start: Int, end: Int): Long = {
var negative: Boolean = false
var i: Int = start
var result: Long = 0L
if (input.charAt(start) == '-') {
negative = true
i += 1
}
val limit: Long = if (negative) Long.MinValue else -Long.MaxValue
val limitMult: Long = limit / 10L
while (i < end) {
val digit: Int = input.charAt(i).toInt - 48
if (i - start < 18) {
result = result * 10L - digit
} else {
if (result < limitMult) {
throw new NumberFormatException(s"For input string: $input")
} else {
result *= 10L
if (digit > 0) {
if (result < limit + digit) {
throw new NumberFormatException(s"For input string: $input")
} else {
result -= digit
}
}
}
}
i += 1
}
if (negative) result else -result
}
@travisbrown
Copy link
Author

travisbrown commented Jun 26, 2017

Adapted (without extra testing) from an implementation I'm planning to use in circe. Note that it can be a little looser than Long.parseLong since the fact that we know that the input is a valid JSON number means we don't have to rule out e.g. "00". For these benchmarks:

val input: CharSequence = "xxxxxxxxxxxx12345678901234567xxxxxxxxxx"
val number: CharSequence = "12345678901234567"

@Benchmark
def parseFast: Long = parseLong(number, 0, number.length)

@Benchmark
def parseStd: Long = java.lang.Long.parseLong(number.toString)

@Benchmark
def parsePartFast: Long = parseLong(input, 12, 29)

@Benchmark
def parsePartStd: Long = java.lang.Long.parseLong(input.subSequence(12, 29).toString)

I get these results:

Benchmark                      Mode  Cnt         Score         Error  Units

LongsBenchmark.parseFast      thrpt   40  63143333.013 ±  940495.494  ops/s
LongsBenchmark.parseStd       thrpt   40  22160978.906 ±  832185.246  ops/s

LongsBenchmark.parsePartFast  thrpt   40  63238647.329 ± 1066086.129  ops/s
LongsBenchmark.parsePartStd   thrpt   40  19805971.734 ±  230489.881  ops/s

@tixxit
Copy link

tixxit commented Jun 26, 2017

Probably wont' have an effect, but I'd be interested in seeing how moving all the "if (negative)" logic into the first branch affects performance. Like,

var limit = -Long.MaxValue
var finalMult = 1

if (input.charAt(start) == '-') {
  limit = Long.MinValue
  finalMult = -1L
  i = 1
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment