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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

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.

Answer 5

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.

Answer 6

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.