14

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?

Improve this question
3
  • GetThingFromDatabase() is not slow enough to make this controversial. Factor4096BitPublicKey();return 1; would make things a bit more interesting. Commented Feb 10, 2013 at 9:46
  • Barbara Liskov is very specific about what is and isn't covered. Commented Feb 18, 2013 at 4:15
  • 1
    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. Commented Nov 10, 2013 at 20:08

6 Answers 6

Reset to default
16

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.

Improve this answer
4
  • 3
    Performance isn't something enforceable via a type check. It a promise of the implementer/library maintainer. Commented Feb 10, 2013 at 9:13
  • 3
    I explicitly stated so in my answer? Commented Feb 10, 2013 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. Commented Feb 10, 2013 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. Commented Feb 11, 2013 at 9:48
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.

Improve this answer
3
  • 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. Commented Sep 6, 2013 at 6: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. Commented Mar 25, 2014 at 0: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". Commented Apr 12, 2016 at 12:35
6

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.

Improve this answer
4

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.

Improve this answer
2

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.

Improve this answer
1
  • 2
    as far as I can tell, example posted is not Java Commented Feb 10, 2013 at 9:45
1

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.

Improve this answer

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.