-2

I have a simple list in Java that I need to search using one of two methods. The first method simply returns the position in the list of the first matching element. The second filters out any elements that don't match. Here's some pseudo-ish-code:

public int positionMatch(String search) {

    for (Element e: myList) {
        if (matches(search, e)) return position(e);
    }
}

public List<Element> filterMatch(String search) {

    for (Element e: myList) {
        if (matches(search, e)) filteredList.add(e);
    }
}

public boolean matches(String search, Element element) {
    // Some logic to determine whether or not the element
    // matches the search term, which is the core functionality
    // shared across all search types. This is ~100 LOC.
}

The problem comes with the calls to match(String search, Element e). My list is tens of thousands of elements, and having a function call per element is causing extreme slowness (by a factor of about 500). The problem is that the search logic in matches(search, e) is shared, regardless of how the elements are returned (either as a position or as a filtered list), and so it doesn't make sense to me to duplicate the code for each method positionMatch and filterMatch (and any other search type that might be added later). However, the performance hit in not duplicating the code is unacceptable.

Another problem is that, at least in Java, you can't have multiple return types (or at least it wouldn't be very pretty or intuitive using generics). Thus, I can't just have a match(String search, List<Element> elements, SearchType searchType) kind of function that would return either an int position or List<Element> filteredList.

Is it okay in this case to duplicate the code across positionMatch and filterMatch in order to void the tens of thousands of function calls to the common code that is causing the slowness?

Or, am I missing something very simple here that could avoid the duplication and not cause performance issues? PS - I am currently writing up a question on CodeReview to see if there is a Java-specific way to avoid this problem...

closed as off-topic by Doc Brown, user7043, Chris Cirefice, Thomas Owens May 30 '16 at 21:26

  • This question does not appear to be about software engineering within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 5
    "My list is tens of thousands of elements, and having a function call per element is causing extreme slowness (by a factor of about 500)." Not a chance. There's no way there is that much overhead to having a function call there, something else must be going on. What has led you the conclusion that it its that expensive? – Winston Ewert May 30 '16 at 21:02
  • @WinstonEwert This is running on an Android phone; I had the code duplicated exactly between both search methods. Each search method ran in about 200 ms. I then moved said code to its own method, and called the method on each Element, which slowed execution down to 10s. So, I'm guessing that, since I didn't do anything else at all, that the function calls are the cause of the problem. The list is currently 70k elements. – Chris Cirefice May 30 '16 at 21:05
  • 1
    @ChrisCirefice That's so incredibly unlikely that you should search really long and hard for other causes of this difference. Even if it's not optimized at all (unlikely), a call just pushes a couple values to the stack, jumps (perhaps indirectly) to the code, and at the end restores the stack. We're talking about less than a hundred instructions, and this is a quite generous estimate. Additionally accounting for the worst possible side effects w.r.t. caching, branch prediction, pipelining, etc. yields at most a few hundred more cycles I'd say. Even 1k cycles take only 1 ms at 1 GHz. – user7043 May 30 '16 at 21:14
  • 1
    @DocBrown I wish! It was just me being stupid and not looking at the one-liner regex test I was doing on the search string; that code was being used once in each of the search functions, but when I removed duplication it ended up being in the match method which was called 70k times. Moving that line back out fixed the 500-factor difference. However, the function calls still cause about a 400ms processing time for 70k elements. – Chris Cirefice May 30 '16 at 21:16
  • 5
    I'm voting to close this question as off-topic because the OP already admitted in a comment his problem had completely different root cause than he presented here ;-). – Doc Brown May 30 '16 at 21:17
4

Wow. Function calls are slower than string searches? What implementation of Java are you using?

I used to write assembly, and the manual would tell how many "clicks" each instruction took on the processor. Those days are gone, but if I had to guess how many clicks various operations take, I'd guess something like the following:

bitwise operations: 1
function call: 2
addition/subtraction: 2
multiplication/division: 10
boxing/unboxing: 10 per box/unbox
find-character-in-string: string-length * 3
regex processing: string-length * 100

When I tested the Java RegEx processor against the Perl one in 2004, Perl was about 100 times faster. I only tested with ASCII and Java uses UTF-16 internally, so that might be part of the reason.

If you were delegating through 10 functions at different levels in the inheritance hierarchy, that might be worth having on your radar if you don't use regular expressions or boxing anywhere.

Also, if you're matching a fixed string within another string, I assume you're using the built-in oneString.indexOf(anotherString) because that's pretty darn speedy.

Have you used a profiler to see where the slowness is actually happening? Or figure out the smallest piece of code you can comment out to make it run fast. If you're on Windows, writing to the terminal is hugely expensive (maybe scores 50 "clicks" in my list above), but on a *nix-based system, for coarse timings, you should be able to:

long startTime = System.nanoTime();
// do something
System.out.println("That thing took " + (System.nanoTime() - startTime));

In Java, you can't have multiple return types (or at least it wouldn't be very pretty or intuitive using generics). Thus, I can't just have a match(String search, List elements, SearchType searchType) kind of function that would return either an int position or List filteredList

public Or<List<Element>,Integer> match(...)

UncleJim has Or under the apache license which you can just copy into your project (with a note of attribution). If that's too opinionated for you, there's OneOf2 where both options are "correct" (a union type). If you want to do the monad-thing there's rxeither that some people are using on Android.

  • 1
    Welp, I feel stupid. Turns out that in moving that code to its own function to remove duplication, I also moved a regex test to see if the search string was ASCII, which was being called 70k times instead of once. That was definitely the problem. I'm sorry, I should have tested just a bit more before posting... The function calls are slowing down processing time by a factor of 3 on average (200ms --> 600ms for 70k calls), but I don't think that's too big of an issue. – Chris Cirefice May 30 '16 at 21:10
  • @ChrisCirefice Glad you got it figured out. Sometimes it helps just to write about it. I updated my answer with notes about Either/Or return types. – GlenPeterson May 30 '16 at 21:17
  • Thanks! Yes, indeed it does. I guess I was just staring at it for so long, I really didn't think that a one-line regex could possibly be the problem! Thanks for your answer though, I'll keep things like this in mind for the future. – Chris Cirefice May 30 '16 at 21:18
  • 1
    also @glenPeterson re 'the monad thing' (lol) bump for funktonale(github.com/MarioAriasC/funKTionale), I'm using its Either object in some kotlin & Java code and like it. – Groostav Jun 13 '16 at 19:04

Not the answer you're looking for? Browse other questions tagged or ask your own question.