Performance measurements: Parsing dates

[westnordost]

Recently I mentioned that parsing dates in Java is quite slow and that 50% of the total parsing time of OpenStreetMap map data is spent on parsing the dates.

I advertised to do this bigger refactor #2678 because then this would be a good opportunity to get rid of the SimpleDateFormat parsing and use the more performant kotlinx-datetime, which is based on the Java 8 time API, also available on Android (if certain build configurations are made).

So, I now did a measurement to see how slow or fast exactly each method is. Here it is:

Parse method	Average time to parse one date (on one core)
	Samsung S10e Android 10 (2019)	Samsung S4 Mini Plus Android 9 (2015)	Samsung S4 Mini Android 9 (2013)	Sony Xperia Z1 Android 5.1 (2013)
Naïve (and wrong), using substring (no validation)	1 μs	1 μs	1 μs	5 μs
Naïve (and wrong), using a regex	8 μs	39 μs	51 μs	54 μs
GregorianCalendar, using substring (no validation)	2 μs	11 μs	13 μs	26 μs
GregorianCalendar, using a regex	11 μs	56 μs	66 μs	77 μs
SimpleDateFormat	12 μs	53 μs	62 μs	180 μs
LocalDateTime.parse	4 μs	28 μs	32 μs	48 μs
Instant.parse	6 μs	42 μs	55 μs	77 μs

And yeah, even 180 μs appears little, but let's parse 30000 OpenStreetMap elements which each have a date attached and we are at 5.4 seconds for the date parsing alone.

That old 5-7 years old mid-range phones are significantly slower than a relatively recent high-end phone is no surprise.

The naïve (and wrong) parsing that simply splits up the date string is each the bottom-line, it is pretty much not possible to make it any faster than that.
There are two observations:

• The new Java 8 time API (Instant) is 20% to 100% faster, depending on the phone / Android version. SimpleDateFormat (old Java time API) is consistently the slowest.
• On old Android versions (below Android 8), the difference seems to be greater. This leads me to believe that CPU speed is not the only factor here but the Android version as well: The new Java 8 time API is available on Android since API level 26 (Android 8). I find it probable that Google could have backported some performance improvements from the new time API to the old time API (Date, SimpleDateFormat). Could have other reaons of course.

Conclusion

Migrating to kotlinx-datetime which uses the Java 8 time API (using the Instant.parse method) will reduce date parsing time by 10%-50%, for older devices possibly more.

This then will result in a decrease of download times by up to 25%. So, a download that took 20 seconds before will then take just 14 seconds. It will not really have any effect on anything else because that is the only place in the app where dates are parsed (en mass).

Not to mention, this is something that needs to be done anyway if one day an iOS version was made (#1892).

Code

Code used for measuring this

package de.westnordost.streetcomplete

import org.junit.Test
import java.text.SimpleDateFormat
import java.time.Instant
import java.time.LocalDateTime
import java.time.format.DateTimeFormatter
import java.util.*
import kotlin.math.roundToLong
import kotlin.system.measureTimeMillis

class DateParsingPerformanceTest {

    @Test fun dateParsingPerformance() {
        val date = "2015-05-07T09:58:16Z"

        val dateRegex = Regex("(\\d{4})-(\\d{2})-(\\d{2})T(\\d{2}):(\\d{2}):(\\d{2})Z")

        val simpleDateFormat = SimpleDateFormat("yyyy-MM-dd'T'HH:mm:ss'Z'")
        simpleDateFormat.timeZone = TimeZone.getTimeZone("UTC")

        val dateTimeFormatter = DateTimeFormatter.ofPattern("yyyy-MM-dd'T'HH:mm:ss'Z'")

        println("Parsing date: Naïve (and wrong), using substring (no validation) - ${measure {
            val year = date.substring(0,4).toInt()
            val month = date.substring(5,7).toInt()
            val day = date.substring(8,10).toInt()
            val hour = date.substring(11,13).toInt()
            val min = date.substring(14,16).toInt()
            val sec = date.substring(17,18).toInt()
            year*365*(month*31*(day*24*(hour*60*(min*60*(sec*1000)))))
        }} μs")

        println("Parsing date: Naïve (and wrong), using a regex - ${measure {
            val values = dateRegex.matchEntire(date)!!.groupValues
            val year = values[1].toInt()
            val month = values[2].toInt()
            val day = values[3].toInt()
            val hour = values[4].toInt()
            val min = values[5].toInt()
            val sec = values[6].toInt()
            year*365*(month*31*(day*24*(hour*60*(min*60*(sec*1000)))))
        }} μs")

        println("Parsing date: GregorianCalendar, using substring (no validation) - ${measure {
            val year = date.substring(0,4).toInt()
            val month = date.substring(5,7).toInt()
            val day = date.substring(8,10).toInt()
            val hour = date.substring(11,13).toInt()
            val min = date.substring(14,16).toInt()
            val sec = date.substring(17,18).toInt()
            GregorianCalendar(year, month - 1, day, hour, min, sec).time
        }} μs")

        println("Parsing date: GregorianCalendar, using a regex - ${measure {
            val values = dateRegex.matchEntire(date)!!.groupValues
            val year = values[1].toInt()
            val month = values[2].toInt()
            val day = values[3].toInt()
            val hour = values[4].toInt()
            val min = values[5].toInt()
            val sec = values[6].toInt()
            GregorianCalendar(year, month - 1, day, hour, min, sec).time
        }} μs")

        println("Parsing date: SimpleDateFormat - ${measure {
            simpleDateFormat.parse(date)
        }} μs")

        println("Parsing date: LocalDateTime.parse - ${measure {
            LocalDateTime.parse(date, dateTimeFormatter)
        }} μs")

        println("Parsing date: Instant.parse - ${measure {
            Instant.parse(date)
        }} μs")
    }
}
/** Measure how long the block needs for execution on average in microseconds, rounded */
private inline fun measure(block: () -> Unit): Long {
    val iterations = 1_000_000
    val millis = measureTimeMillis { repeat(iterations) { block() } }
    return ((10000 * millis / iterations).toDouble() / 10).roundToLong()
}

[smichel17]

From that bottom line, we see that the Android 5 phone is 5 times slower than the Android 11 one.

I think you've mixed up the numbers somewhere, because in the graphs, the 2019 phone is slower than the 2013 phone.

[smichel17]

Ack, never mind, inconsistent axes strike again!

[Helium314]

Some questions that make me feel a bit stupid...

• Where is date parsing required? Apparently it is necessary for every element, so I guess it is the modification time... but why would this be stored as string and not as a simple (int or long) timestamp?
• Where do I actually put the code if I want to run it on my phone?(I'm curious how a weaker CPU than Xperia Z1, but running Android 9 affects this.)

[westnordost]

I'd also be curious on how it performs on new but slow phones. Did you try it out, @Helium314 ? I could include your measurements in the above table

[Helium314]

Not yet, it will take some longer time before I have physical connection to the PC running Android Studio...
But if you would like to know, I'll try to create some mini-app containing the code.

[westnordost]

How, if you have no access to an Android Studio?

[Helium314]

Remote access is working, but as I understand it for running these test I need to plug my phone to have adb connection.

[Helium314]

So... finally results on my phones running Lineage 16.0:
S4 Mini has a Snapdragon 400 (1.7 GHz, dual core, 32 bit)
S4 Mini Plus has a Snapdragon 410 (1.2 GHz, quad core, 64 bit but Lineage only working as 32 bit version)

method	S4 Mini, 1 core	S4 Mini, 2 cores	S4 Mini Plus, 1 core	S4 Mini Plus, 4 cores
Naïve (and wrong), using substring (no validation)	1 μs	1 μs	2 µs	1 µs
Naïve (and wrong), using a regex	63 μs	51 μs	61 µs	39 µs
GregorianCalendar, using substring (no validation)	25 μs	13 μs	20 µs	11 µs
GregorianCalendar, using a regex	94 μs	66 μs	80 µs	56 µs
SimpleDateFormat	82 µs	62 μs	67 µs	53 µs
LocalDateTime.parse	33 μs	32 μs	30 µs	28 µs
Instant.parse	55 μs	55 μs	46 µs	42 µs

Naïve (and wrong), using substring (no validation) sometimes takes significantly longer. On both phones I ran the tests multiple times and each had one run where this method took 6 or 7 µs.
Other tests are reproducible within ca 10%.

If someone want to run the test, simply extract and install the attached app. Start app, click start test and wait (up to) a few minutes (nothing else in this app is actually working).
The last two tests require Android 8 and will not appear on older versions.

[westnordost]

How did you let it run on multiple cores?

…

On April 15, 2021 11:28:06 AM GMT+02:00, Helium314 ***@***.***> wrote: So... finally results on my phones running Lineage 16.0:> S4 Mini has a Snapdragon 400 (1.7 GHz, dual core)> S4 Mini Plus has a Snapdragon 410 (1.2 GHz, quad core)> > method | S4 Mini, 1 core | S4 Mini, 2 cores | S4 Mini Plus, 1 core | S4 Mini Plus, 4 cores> --|--|--|--|--> Naïve (and wrong), using substring (no validation) | 1 μs | 1 μs | 2 µs | 1 µs> Naïve (and wrong), using a regex | 63 μs | 51 μs | 61 µs | 39 µs> GregorianCalendar, using substring (no validation) | 25 μs | 13 μs | 20 µs | 11 µs> GregorianCalendar, using a regex | 94 μs | 66 μs | 80 µs | 56 µs> SimpleDateFormat | 82 µs | 62 μs | 67 µs | 53 µs> LocalDateTime.parse | 33 μs | 32 μs | 30 µs | 28 µs> Instant.parse | 55 μs | 55 μs | 46 µs | 42 µs> > `Naïve (and wrong), using substring (no validation)` sometimes takes significantly longer. On both phones I ran the tests multiple times and each had one run where this method took 6 or 7 µs.> Other tests are reproducible within ca 10%.> > If someone want to run the test, simply extract and install the attached [app](https://github.com/streetcomplete/StreetComplete/files/6316534/date_parse_test.zip). Start app, click `start test` and wait (up to) a few minutes (nothing else in this app is actually working).> The last two tests require Android 8 and will not appear on older versions.> > -- > You are receiving this because you authored the thread.> Reply to this email directly or view it on GitHub:> #2740 (reply in thread)

-- Diese Nachricht wurde von meinem Android-Gerät mit K-9 Mail gesendet.

[westnordost]

Do you use Kotlin and the code is in a MainActivity? Then easiest would be

thread {
    val results = runTheTests();
    // anything touching the view must execute on the UI thread in Android
    runOnUiThread {
        displayTheResults(results);
    }
}

[Helium314]

Thanks! It's in a fragment, but activity?.runOnUiThread was all that needed to be changed.

When running the phone on a single core this is 20-30% slower, except for both no validation tests.
With all cores active, the last tests are a bit faster (ran the tests twice to confirm)

method	main thread	background thread
SimpleDateFormat	53 µs	51 µs
LocalDateTime.parse	28 µs	27 µs
Instant.parse	42 µs	39 µs

Is a valid timestamp actually required for all elements? If not it could be feasible to exclude some elements from date parsing...

[westnordost]

Ok, so not really any difference then. Thanks!

Yes, a valid timestamp is required for all elements because the downloader does not know how the data will be used.

[smichel17]

Are they serialized before processing, or analyzed while still in memory, and then persisted? If the latter, maybe the date parsing could be done lazily.

[westnordost]

Already considered this