19

Let's say I have a function which sorts a database in O(n^2) time. I want to go about refactoring it so it runs in O(n log(n)) time, and in doing so I will change the fundamental way the operation runs, while keeping the return values and inputs equivalent.

What do I call this refactoring activity?

"Speeding-up-ifying" doesn't seem quite right, since you can make an algorithm go faster without changing the big O speed at which it executed.

"Simplifying" also doesn't seem right.

What do I call this activity?

Update

The best answer I could find is reducing the asympotic time complexity.

Code Whisperer
  • 723
  • 6
  • 10
  • Are the algorithms expected to be faster in most use-cases after the modification? To note it, sometimes it's nice to move to a better-scaling complexity class even at an expected average performance hit, just to get more consistent performance behavior. – Nat Jan 07 '18 at 15:51
  • 22
    This is not refactoring – theonlygusti Jan 07 '18 at 19:28
  • 6
    Strictly speaking, function which runs in `O(log(n))` time also runs in `O(n^2)` time. The meaning of `O(n^2)` is "doesn't grow faster than quadratic." You probably meant Theta(log(n)) which means "grows as fast as `log(n)`". https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann%E2%80%93Landau_notations – Džuris Jan 07 '18 at 20:04
  • The question is poorly posed. The algorithm is being improved or optimized, but the code is therefore being rewritten. – Sentinel Jan 07 '18 at 20:09
  • 4
    you did not change the big o execution time of a function. a function is a relationship between a domain and a codomain and exists independent of your puny human attempts at implementation. instead you found a better performing algorithm that implements the function good job – emory Jan 07 '18 at 21:38
  • This is *Re-Implementation* – S.D. Jan 08 '18 at 07:55
  • 5
    @theonlygusti: It depends. If the function previously made a guarantee / guarantees on complexities, it's not refactoring. If it did not guarantee anything, it's refactoring. If it even was explicit about not making guarantees, it's especially a refactoring. – phresnel Jan 08 '18 at 10:16
  • Technically it is asymptotic performance improvement (which can mean that the actual running times got worse). Otherwise, you could also use "qualitative" (I'd rather avoid that one) or just simply "significant" and then back it up by some benchmark numbers (assuming the running times did get significantly better). – dtldarek Jan 08 '18 at 12:39
  • What in the world do you mean by "sorts a database"? – jpmc26 Jan 08 '18 at 15:40
  • In a profession where terms mean nothing because they're defined differently at every company and every conference and every textbook, why does it matter? – corsiKa Jan 08 '18 at 16:34

6 Answers6

44

It is typically called "performance optimization", but I would not call it "refactoring", since this term typically refers to changes in code which don't change its visible behaviour. And a change in Big-O is definitely something which I would call a visible change.

in doing so I will change the fundamental way the operation runs

In this case, your optimization is a rewrite of that function. Not every optimization, even if it changes "Big-O", is necessarily a rewrite, sometimes only small changes are necessary to achieve such an improvement, but even then, I am reluctant to use the term "refactoring" for this, because it tends to give a wrong impression about the nature of the change.

EDIT: I checked Fowler's refactoring list, and among this ~100 named refactorings, the very last one is called "Substitute Algorithm". So if we take this as canonical reference, there is a small, grey area where an optimization of the described form might be called a special kind of refactoring (but IMHO not a typical one). Note also, Fowler's goal with all refactorings was always to improve the design with focus on maintainability and evolvability of existing code without rewriting it, and clearly not performance optimization.

Doc Brown
  • 199,015
  • 33
  • 367
  • 565
  • 10
    really? I would think refactoring is correct unless the requirements change. So.. No if the function is called BubbleSort, but yes if its just Sort – Ewan Jan 07 '18 at 16:50
  • 3
    @Ewan Yes, legalistically a refactoring can be a performance-optimization, but the former is far too general and doesn't appropriately capture the changes impact. – Deduplicator Jan 07 '18 at 17:50
  • @Ewan, I'd say that "refactoring" is not a term that applies to fundamentally changing an algorithm, unless it is literally an identical algorithm with its variables just rearranged. For example, an algorithm that says "get constant A, get constant B, return A+B" is refactored if it merely changes to "get constant B, get constant A, return A+B" (and if the ordering of retrieval could never be significant for the application). But if the algorithm uses fundamentally different approach, like changing a sequential search into a binary chop, that is a complete reimplementation of that function. – Steve Jan 07 '18 at 18:53
  • my concern is that that view relegates 'refactoring' to mear changes of variable names and the like. Surely we can refactor for performance or other non-functional requirements like security – Ewan Jan 07 '18 at 18:56
  • @Ewan, yes, the classic "refactor" for structured code is to break a large method into several smaller ones, or move repeated code into it's own method, or introduce intermediate variables with good names to make an algorithm clearer. It could be a previous change, or an accumulation of them, that make this necessary. The purpose is to improve the ability to understand and reason about the source code. But often source code is not being refactored, and may not be particularly poorly factored to start with, it is just being tuned, or even ripped out and replaced by something (hopefully) better. – Steve Jan 07 '18 at 19:28
  • 1
    I was at an early presentation by the guy who invented and coined Refactoring (Fowler?) and the whole idea was connected to automatic programming and provable verifiable improvements to code that had no effect on input vs output. – Sentinel Jan 07 '18 at 20:03
  • To all of you: see my edit. – Doc Brown Jan 07 '18 at 20:06
  • @DocBrown, if you actually look at the definition given of "substitute algorithm", it talks of replacing the algorithm *in a method* with one that is *clearer* - not better or more performant. So I think Fowler's list proves our position that refactoring is something that is done to improve the clarity of source code, not to adjust it's function. Otherwise, "substitute algorithm" becomes the "and everything else" component - and completely ripping up the entire source code of a program and rewriting it from scratch could still be seen as merely refactoring with a "substitute algorithm". – Steve Jan 07 '18 at 21:40
  • @Sentinel, there's no doubt that refactoring is related to code improvement - it's just not the *same as* improvement. Nobody refactors code for its own sake, but does so in order to preserve it's long-term maintainability or to create the potential for further improvements (having recognised that these qualities are being impugned by the obscurity or poor structure of source code). But for code that is already adequately factored, improvements can be made with minimal or no refactoring of existing code. – Steve Jan 07 '18 at 21:47
  • 1
    @Steve. Agreed. I was merely adding to the consensus that Big O improvements represent algorithmic improvement, not improvements to how those algorithms are represented or maintained. In other words, the activity is a *rewrite* – Sentinel Jan 07 '18 at 23:02
  • 1
    @Steve: yes, I knew that, thought about adding a note to my answer. My edit was just a note to make clear there is a small, grey area. – Doc Brown Jan 08 '18 at 06:46
  • [Wikipedia](https://en.wikipedia.org/wiki/Code_refactoring) indicates that refactoring involves changing [nonfunctional requirements](https://en.wikipedia.org/wiki/Non-functional_requirement), of which performance is one. Bottom line: refactoring is *far* too vague and general a term to exclude much of anything from it. The only thing I would try to exclude from the term "refactoring" is additions that don't change existing code structures at all. So can we not waste effort trying to nitpick over terms that aren't strictly defined, please? – jpmc26 Jan 08 '18 at 15:44
  • @jpmc26: this Wikipedia definition clearly does not say "refactoring is any kind of change of nonfunctional requirements", it says *"Refactoring improves nonfunctional attributes of the software"*, which in context of the sentence before *"without changing its external behavior"* clearly means "**some** nonfunctional attributes of the software, not **any**". Moreover, Wikipedia is not the canonical reference for me. Fowler, who invented the term, wrote a book with that title, and made the catalog I linked to in my answer, is. – Doc Brown Jan 08 '18 at 15:51
  • @DocBrown ...Did you miss the part about not nitpicking over terms that aren't strictly defined? It also says, "Typically, refactoring applies a series of standardised basic micro-refactorings," which is a bunch of horse hockey; the term is used far more generally than that. – jpmc26 Jan 08 '18 at 15:54
  • @jpmc26: honestly, I think you took these half-sentences out of their context. And just because something is not 100% strictly defined, it does not mean it has an arbitrary meaning. – Doc Brown Jan 08 '18 at 15:59
13

I don't think there is a standard term, a commonly used is optimizing though improving, or speeding up would also be correct making the clarification that you are talking about code changes and not hardware changes.

ichantz
  • 368
  • 1
  • 8
7

As others have said, "optimizing" is the general term for improving the performance of an algorithm. However, optimizing often means improving constant factors. If I wanted to concisely but clearly state that I've reduced the asymptotic (time) complexity, I'd say that I've "improved the asymptotic performance". Sometimes people will describe this as "improving the scaling" but this is especially ambiguous nowadays.

Warning: Reducing the asymptotic time complexity is not necessarily the same as optimizing in a practical context. Oftentimes asymptotically non-optimal algorithms are used because on the range of inputs the program actually is exposed to the less optimal algorithms perform better.

Derek Elkins left SE
  • 6,591
  • 2
  • 13
  • 21
5

It will be context-dependent.

"Fixing a quadratic runtime performance bug" is typically what I see. However, whether that deserves fixing (a code change) is context-dependent.

Keep in mind that databases provide lots of tools to improve time complexity. For example, to get the top N results from a database, just say so. When converting inefficient kludge into built-in optimized call, explanation seems superfluous.

The reason I consider an algorithm with quadratic runtime to deserve a code review (discussion) is not so much because it is slow (slow is relative; quadratic is fast when compared to exponential), but because human intuition (such as your customers, or fellow programmers) are innately uncomfortable with a software functionality that deviates too far from linear runtime, due to mixing of expectations from everyday life.

A lot of customer complaints about software performance falls into these two categories:

  • The whole system (software and hardware) were specified based on estimated usage. Last week, everything runs fine, a certain functionality took less than 5 seconds. This week, after installing an update, the same functionality takes more than 1 minute.

    • This is a comparison with a previously benchmarked performance. The customer holds future performance to an absolute yardstick of a human time-scale (from seconds to minute).

  • I submitted 100 jobs to the system. Why is it taking 400x the time to process, compared to the time it takes for a single job?

    • The customer expects processing time to be linear. In fact, the customer cannot understand or accept that there exists tasks that are slower than linear.

For this reason, a customer will consider the execution time to be a bug if both are true:

  • Slower than linear
  • Noticeable (i.e. falls within the human time range (longer than seconds or minutes) given typical task sizes)

Legitimate arguments that explain that a quadratic runtime algorithm doesn't pose a problem (i.e. doesn't deserve a code change):

  • The size of task typically handled by this quadratic runtime function is somewhat bounded
  • Given the typical size range, the actual (absolute) execution time is still small enough to be dismissed
  • If a user actually tries to submit a task that is large enough to be noticeable, the user will receive a message warning about the long running time
  • The users of the system are all experts, therefore they know what they are doing. For example, users of an API should have read the fine print on the API documentation.

A lot of algorithms useful for typical application development are in fact slower than linear (mostly O(N log N), as in sorting), therefore large-scale software will in fact try to workaround that, by only sorting the relevant part of the data, or use histogram (statistical) filtering techniques which achieves similar effect.

This applies to software customers, but if you consider the users of a software library or API function to be "customers" as well, then the answer would still apply.

rwong
  • 16,695
  • 3
  • 33
  • 81
2

If the original algorithm was correctly implemented (or any bugs where irrelevant) then "changing the algorithm" or "algorithm substitution", since such changes mean you are doing precisely that; substituting an algorithm with different time complexity for the one previously used.

If the previous time complexity was due to a bug in the implementation (e.g. say you were accidentally resetting the starting point of an inner loop on a sequence so that what should have been O(n) became O(n2)) then "fixing a quadratic cost bug" or similar.

There's an overlap, in that in such a case the effect on the code is the same if you know from the outset that the work could be done in O(n) time and the O(n2) time was an error, or if you first deliberately implemented it in O(n2) time and then realised it would still work correctly without resetting the starting point, and so substituted an O(n) algorithm for an O(n2) one.

Jon Hanna
  • 2,115
  • 12
  • 15
1

Speed optimization by an order/orders of magnitude. Though this is mathematically incorrect language, it best conveys the idea of the Order being changed.

Improved the scalability. heard also.

Joop Eggen
  • 2,011
  • 12
  • 10