Regex vs IndexOf in Java.

By

Overview

The author of these articles Are C# .Net Regular Expressions Fast Enough for You? and .Net Regex: Can Regular Expression Parsing be Faster than XmlDocument or Linq to Xml? recently pointed out to me that he had found that Regular expressions were at least as fast or faster than the alternatives in C#. However it has been my experience that regular expressions in Java were slower. It is hard for me to say why this might be different in Java and C# or even if these are fair comparisons but here is what I found in Java.

Searching XML for the start of a field

This test searches for the expression "\\s*" in short section of text. 
Performing 1 loops, regex took 323.389 us and indexOf took 73.026 us on average, ratio=4.4
Performing 10 loops, regex took 61.513 us and indexOf took 42.480 us on average, ratio=1.4
Performing 100 loops, regex took 84.899 us and indexOf took 8.134 us on average, ratio=10.4
Performing 1,000 loops, regex took 16.307 us and indexOf took 5.851 us on average, ratio=2.8
Performing 10,000 loops, regex took 3.751 us and indexOf took 1.321 us on average, ratio=2.8
Performing 100,000 loops, regex took 3.586 us and indexOf took 1.260 us on average, ratio=2.8
Using indexOf is somewhat faster, but more complex to code. You would only optimise this example if you really needed to as even one million searches takes a fraction of a second.

Code for Search XML example

Searching for a value= expression in a short string

This test search for the {value} in value="{value}" of a short string. 
Performing 1 loops, regex took 227.029 us and indexOf took 9.387 us on average, ratio=24.2
Performing 10 loops, regex took 11.141 us and indexOf took 1.195 us on average, ratio=9.3
Performing 100 loops, regex took 9.631 us and indexOf took 1.108 us on average, ratio=8.7
Performing 1,000 loops, regex took 14.993 us and indexOf took 2.491 us on average, ratio=6.0
Performing 10,000 loops, regex took 2.472 us and indexOf took 0.254 us on average, ratio=9.7
Performing 100,000 loops, regex took 0.583 us and indexOf took 0.097 us on average, ratio=6.0
Performing 100,000 loops, regex took 0.465 us and indexOf took 0.032 us on average, ratio=14.5
Performing 100,000 loops, regex took 0.467 us and indexOf took 0.032 us on average, ratio=14.6
Since the times keep improving even after 100K iterations, I suspect the JIT is able to optimise indexOf more than the relatively complex code supporting regular expressions.

Code for Searching a short string example

Comments

  1. OmegaMan2 January 2012 at 20:03

    Hey Peter, Great post! :-) Give some time for a reply. -Bill

    ReplyDelete
  2. Peter Lawrey3 January 2012 at 08:17

    @OmegaMan I thought your articles worthy of a well thought out reply. ;)

    ReplyDelete
  3. Unknown3 January 2012 at 08:47

    hi Peter, this link can be worth looking at in regards to regex performance:

    http://tusker.org/regex/regex_benchmark.html

    built-in implementation definitely is not the fastest possible.

    ReplyDelete
  4. jay6 January 2012 at 12:10

    Your second link "Code for Searching a short string example" does not work as of the date of this comment.

    ReplyDelete
  5. Peter Lawrey6 January 2012 at 15:10

    @jay, It is working for me now. Perhaps if you try it again?

    You could try http://code.google.com/p/core-java-performance-examples/source/browse/trunk/src/test/java/com/google/code/java/core/regex/ which is the parent directory for both code examples.

    ReplyDelete
  6. jay7 January 2012 at 10:19

    Weird...the link didn't start working for me until I access the link you provided in the comment.

    Anyway, in the second example, by
    1. using this pattern: "value=\"([^\"]+?)"
    2. Creating the Matcher once and using matcher.reset() inside the for loop
    3. Passing in the Pattern instead of recompiling it in the function

    I reduced the last ratio from 10.7 to around 3. But my laptop is slower (originally 0.766 us vs. 0.467 on your machine for the regex)

    ReplyDelete
  7. Peter Lawrey7 January 2012 at 10:47

    An assumption I am making is you wouldn't actually want to parse the same string repeatedly, otherwise you would cache the result. What this should really test is a String which can change. Reusing a compiled Pattern makes sense, but I suspect isn't taking much time.

    Is it possible to re-use a Matcher with different Strings?

    ReplyDelete
  8. jay7 January 2012 at 11:18

    Yes, it is possible to reuse a Matcher with different Strings:

    matcher.reset(myNewString);

    By the way, I just found your blog yesterday and have enjoyed what I have read so far. Thanks!

    ReplyDelete

Post a Comment

Popular posts from this blog

Java is Very Fast, If You Don’t Create Many Objects

By
Image
  You still have to watch how many objects you create. This article looks at a benchmark passing events over TCP/IP at 4 billion events per minute using the net.openhft.chronicle.wire.channel package in Chronicle Wire and why we still avoid object allocations..  One of the key optimisations is creating almost no garbage. Allocation is a very cheap operation and collection of very short-lived objects is also very cheap. Does this really make a difference? What difference does one small object per event (44 bytes) make to the performance in a throughput test where GC pauses are amortised? While allocation is as efficient as possible, it doesn’t avoid the memory pressure on the L1/L2 caches of your CPUs and when many cores are busy, they are contending for memory in the shared L3 cache.  Results Benchmark on a Ryzen 5950X with Ubuntu 22.10. JVM Vendor, Version No objects Throughput, Average Latency* One object per event Throughput, Average Latency* Azul Zulu 1.8.0_322 60.6 M event/s, 528
Read more

System wide unique nanosecond timestamps

By
A Unique Identifier can be very useful for tracing. Those ids are even more useful when they contain a high-resolution timestamp.  Not only do they record the time of an event, but if unique can help trace events as they pass through the system. Such unique timestamps however can be expensive depending on how they are implemented.   This post explores a lightweight means of producing a unique, monotonically increasing system-wide nano-second resolution timestamp available in our open-source library. Uses for Unique Identifiers Unique identifiers can be useful to associate with a piece of information so that information can be referred to later unambiguously. This could be an event, a request, an order id, or a customer id. They can naturally be used as a primary key in a database or key/value store to retrieve that information later. One of the challenges of generating these identifiers is avoiding creating duplicates while not having an increasing cost.  You could record every identi
Read more

Comparing Approaches to Durability in Low Latency Messaging Queues

By
Image
  A significant feature of Chronicle Queue Enterprise is support for TCP replication across multiple servers to ensure the high availability of application infrastructure. I generally believe that replicating data to a secondary system is faster than syncing to disk, assuming the round trip network delay wasn’t high due to quality networks and co-located redundant servers. This is the first time I have benchmarked it with a realistic example. Little’s Law and Why Latency Matters In many cases, the assumption is that the latency won't be a problem as long as throughput is high enough. However, latency is often a key factor in why the throughput isn’t high enough. Little’s law states, “ the long-term average number  L  of customers in a  stationary  system is equal to the long-term average effective arrival rate  λ  multiplied by the average time  W  that a customer spends in the system”. In computer terminology, the level of concurrency or parallelism a system has to support must be
Read more