Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

If I have a variable containing a List it could contain objects of a lot of different types e.g. ArrayList or LinkedList. The difference between a LinkedList and an ArrayList is pretty big. The big O behavior of the methods differs greatly. For example sorting the List and then using it to do binary searches is perfectly ok for an ArrayList but would not make sense with a LinkedList.

share|improve this question
    
What does "the big O" mean ? –  user61852 Jul 11 '13 at 11:50
    
@user61852 en.wikipedia.org/wiki/Big_O_notation –  Paling Jul 11 '13 at 17:50

4 Answers 4

I wouldn't say so.

A leaky abstraction is one that forces you to deal with implementation details that it's supposed to abstract away. But performance always differs between implementations, so if you count that as leaking, then there are no non-leaking abstractions.

If something is declared as List without further documentation, it should be understood that there are simply no guarantees about performance, and if you're going to do anything performance-sensitive with it, you should make a copy and work with that.

Also, don't forget that there's an even more general interface that is often sufficient in functionality and does not tempt you to make as many assumptions about performance: Collection.

share|improve this answer
9  
There is an even more general interface that is often sufficient in functionality: Iterable. –  emory Jul 10 '13 at 13:15
    
Performance differences between the different implementations are expected. E.g. there are differences between Vector and ArrayList, but a get operation on a LinkedList just seems strange. –  Paling Jul 11 '13 at 7:33

All non-trivial abstractions, to some degree, are leaky. That said, I'm not really sure it applies here. :-)

Abstractions are concerned with behaviour. Unless the behaviour specifies particular performance (which Java's List does not) it's an implementation detail - i.e. irrelevant.

Java doesn't allow you to specify minimum performance for interfaces outside of documentation, and I'm not aware of any languages which do - it would be incredibly hard (impossible?) for the compiler to verify. I can see a couple of options if performance is a concern:

  1. Document it in the class/interface the list instance will belong to.
  2. Create a new interface - e.g. BinarySearchPerformantList (yuck!) - which specifies the performance requirements of the various methods.

Option 2 is probably the better abstraction, but comes with extra overhead.

share|improve this answer
1  
+1. Technically yes, a List is a leaky abstraction, but then so is Object for hiding complexity related to using equals to compare objects. –  Neil Jul 10 '13 at 10:40
2  
@Neil I think it's debatable... Since the abstraction doesn't mention performance I don't think it's failing in this case (as I've argued). I'd say that if you're thinking about performance you need a different/narrower abstraction. Will edit to mention that. –  Baqueta Jul 10 '13 at 11:04
    
It depends on what you're hiding I suppose. Is complexity in the usage or is it in its memory usage and implementation? Because if it is an abstract class, one or more of these complexities is getting hidden in one way or another. –  Neil Jul 10 '13 at 12:00
    
I played around many years back implementing a variation of Option 2 using marker interfaces like LinearSpace and LogarithmicTime and then declaring classes like public class BinarySearch : ISearchStrategy<T>, LogarithmicTime. Other classes could take parameters like public T find<T, S>(IList<T> list, S strategy) where S : ISearchStrategy<T>, LogarithmicTime { } to enforce performance constraints. –  Lucas Jul 10 '13 at 13:28
2  
If we're going by the Joel Spolsky article, I think it is "to some degree, leaky". See the following quote from the article: "If you were curt with the system administrators in your company and they punished you by plugging you into an overloaded hub, only some of your IP packets will get through, and TCP will work, but everything will be really slow" I think this applies –  Amish Programmer Jul 10 '13 at 13:54

You are correct, a List is a leaky abstraction. The STL uses the idea of concepts to model this specific problem. To use your example, an ArrayList models a Random Access Iterator while a LinkedList models a Forward Iterator. Different concepts have different performance requirements, which make them appropriate for different algorithms.

share|improve this answer

In Java, there is a RandomAccess interface which is defined as a list with generally constant random access time (O(1) get, put etc.). If you feel that your module requires a list with those performance characteristics, consider using RandomAccess instead of List. If you don't feel the need to make that change (and few do), then perhaps List is not so leaky.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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