Do changes in performance violate the Liskov Substitution Principle?

Question

Say I have:

interface Thing
{
    GetThing();
}

class FastThing : Thing 
{
    public int GetThing()
    {
        return 1;
    }
}

class SlowThing : Thing
{
    public int GetThing()
    {
        return GetThingFromDatabase();
    }
}

Is this a violation of the Liskov Substitution Principle?

GetThingFromDatabase() is not slow enough to make this controversial. Factor4096BitPublicKey();return 1; would make things a bit more interesting. — Patrick, Feb 10 '13 at 09:46
Barbara Liskov is very specific about what is and isn't covered. — snakehiss, Feb 18 '13 at 04:15
If you replace FastThing with SlowThing, the LSP does not apply. If you add a comment to Thing::GetThing which says "Is very fast", the question can be discussed. — Cephalopod, Nov 10 '13 at 20:08

score 15 · Accepted Answer · answered Feb 09 '13 at 23:42

15

That really depends. Some interfaces have, for example, complexity constraints (these obviously can't be programmatically enforced). The most basic case is "GetThing() gives an int- i.e., it halts", in which case, the answer would be "No"- both versions of GetThing() halt and return an int.

But many interfaces have implied or expressly stated performance guarantees, either in complexity or in flat time. For example, in the C++ Standard, it's illegal to implement the library with a blocking call except where the Standard expressly permits.

answered Feb 09 '13 at 23:42

DeadMG

36,902

3

Performance isn't something enforceable via a type check. It a promise of the implementer/library maintainer. – snakehiss Feb 10 '13 at 09:13
3

I explicitly stated so in my answer? – DeadMG Feb 10 '13 at 11:30
1

My point was that as soon as you include anything other than type in the criteria you are no longer talking about Liskov as it is specific to type. While the "practice" of not subbing out differently performing objects may be good, Liskov itself has nothing to say about it. – snakehiss Feb 10 '13 at 21:18
8

Liskov states that for the Derived, it should be usable anywhere a Base is. That may well not be true if the Base guarantees certain performances or characteristics. For example, if Derived blocks, there may be the potential for deadlocks. – DeadMG Feb 11 '13 at 09:48

snakehiss · Answer 2 · 2023-07-28T19:06:23.107

9

TL;DR: No

According to the "Behavioral Subtyping Using Invariants and Constraints" (the formalization of the principle) it is primarily concerned with "safety" properties of an objects type. Properties which govern substitutability only within the context of type information. An objects type is orthogonal to it's performance. Therefore a difference in performance is not a violation of the Liskov Substitution Principle.

edited Jul 28 '23 at 19:06

answered Feb 10 '13 at 00:00

snakehiss

8,697

3

I had only a short look into that paper, but are you sure that timing constraints cannot be made formally provable? And even if Liskov did not mean that in words, including timing constraints could be seen as a good extension of the classical LSP which may be relevant to real-world programming. – Doc Brown Sep 06 '13 at 06:40
@Doc Brown: whether timing is useful as a consideration to substituting an object or not is orthogonal to Liskov. To can add it as a sperate precept, but it cannot and will never be part of Liskov. It's like having a Boolean logic equation and saying !False can only be substituted by True if it's fast enough. Speed has nothing to do with math or logic. – snakehiss Mar 25 '14 at 00:54
Counterexample: this code is called in Java's EDT, or in Node's event loop. The radically slower performance of the slow version will semi-break the software. I think the proper answer to this question is "probably not but there are exceptions". – user949300 Apr 12 '16 at 12:35

score 6 · Answer 3 · answered Feb 10 '13 at 02:20

What guarantees does the interface make? Since GetThing makes no guarantees then subtypes need not respect it.

If the interface was something like GetThingInLinearTime or if the base type is virtual and the default implementation is one complexity, then making that algorithmic complexity worse would violate LSP.

score 4 · Answer 4 · answered Feb 10 '13 at 00:04

The performance of the software has nothing to do with the Liskov Substitution Principle.

The principle has to do with substitution of subtypes, and the behavioral impact of substituting that object in OOP terms only.

The input and output of getThing() remain the same for both cases, and both slow and fast likely put the objects into the same state.

score 2 · Answer 5 · answered Feb 10 '13 at 02:32

Does it matter what the Liskov Substitution Principle itself says specifically? If a subtype violates the expectations of the consumer of the supertype, that seems like a bad thing regardless of whether LSP is more restrictive.

So in my view, whether all reasonable expectations of the consumer of an abstraction are fulfilled by the subtype seems to be a good generalization of LSP.

However, in the example you have posted and with Java interfaces in general, it's not clear that the consumer of the Thing interface has any reasonable expectation of whether it should be fast or slow. If the interface's javadocs were to include language about what operations are promised to be fast, then there might be an argument for a problem on performance grounds. But the Java convention is certainly for various implementations to have different performance characteristics.

as far as I can tell, example posted is not Java – gnat Feb 10 '13 at 09:45 — gnat, Feb 10 '13 at 09:45

score 1 · Answer 6 · answered Jul 29 '23 at 11:40

It depends. At some point performance is actually part of the behaviour. For example, if you have two classes calculating Fibonacci numbers, one uses linear time and the other uses exponential time, then you can’t substitute the second one for the first one. If you have a dictionary class using a hash and one doing a linear search, substituting the second one might change behaviour from “runs nice and smooth” to “takes forever and customers complain and ask for a refund”.

If both classes are “fast enough” then you are fine.

Do changes in performance violate the Liskov Substitution Principle?

6 Answers6