4 ms·

Can you say more about the important performance ramifications?

• colanderman 10y ago
  Dynamic homogeneous structures (lists) have uniform structure, but must be able to resize dynamically. The former helps performance (run-time type info can be hoisted out of the structure), the latter harms it (extra runtime machinery needed). Static heterogeneous structures (tuples) have a non-uniform structure, but need not resize. The former harms performance (run-time type info must be kept for each element, though usually few); the latter helps it (most accesses can be compiled to simple pointer arithmetic). On the other hand, dynamic heterogeneous structures (Python's lists) do not have uniform structure, and must be able to resize. So run-time type info must be preserved (adding memory/access overhead), and accesses can't be optimized at compile time (more runtime machinery). It is to avoid these issues that things like numpy and JavaScript's typed arrays exist. There is almost never a reason to use a dynamic heterogeneous structure, so they are best avoided. A dynamic heterogeneous collection can neither support indexing a priori known components (since it is dynamic), nor support iteration (since it is heterogeneous). (Note that a collection of objects of different types but with a shared interface is in fact a homogeneous collection of objects with that interface.) (The final combination is static homogeneous, but these are a subset of both the first two cases, and do not occur often. The only example I can think of are sets of statistics: all statistics have the same type, but there are a fixed number of them which are known at compile time. They can be optimized very well.)
  • pdonis 10y ago
    Python only has what you call "dynamic heterogeneous" structures because Python is a dynamic language. The ramifications of that are by no means limited to lists and tuples. It seems like you basically don't like dynamic languages. Some of your comments make no sense even given the above, however. For example, Python lists and tuples certainly support iteration.
    • colanderman 10y ago
      Erlang (one of my favorite languages) is dynamically typed, yet did not (until the recent addition of maps) have dynamic heterogeneous structures. You cannot iterate over or resize tuples, and the static analyzer discourages heterogeneous lists. Both are immutable (functional). I apologize that I have hopped between use and implementation a bit in my above post. Yes, the implementation of Python lists and tuples support iteration, but it would be nonsensical to write code which iterated over a list or tuple containing heterogeneous data. (What could you possibly do identically to each element, if they had nothing in common?) Hence my assertion that implementing a dynamic heterogeneous structure is inefficient, if it nonsensical to truly use it as such.
      • markrages 10y ago
        > it would be nonsensical to write code which iterated over a list or tuple containing heterogeneous data. There are Python functions that take any type like repr() or id()
        • colanderman 10y ago
          See my other comment; it does make sense to have a list of objects which share some interface. In the case you suggest, it is a very trivial and not-very-useful interface, but an interface nonetheless. You can do this with objects even in strictly-typed languages like OCaml or Mercury; code which iterates over the list is simply restricted to use only those methods which all elements have in common. Of course in languages which don't support a universal "object" type (say OCaml or C) you cannot do this -- numbers and strings have no interface in common. Those languages take advantage of this by not storing type information in collections (e.g. OCaml's float arrays, or any array in C), thus resulting in more compact memory footprints. If they instead allowed heterogeneous collections, the memory footprint of such collections would double.
        • aangjie 10y ago
          > There are Python functions that take any type like repr() or id() Umm.. I haven't had to use any of them on a list(or for that matter on an object) for code.. (except when I'm curious and poking at python internals) May be I'm stuck in a web application role? Is it actually useful to say call repr() on a list of objects? May be call id to see if there's references to same object twice? I'm finding it hard to imagine cases where it would be needed to implement a feature, that wouldn't be better served by alternate methods.
  • nedbat 10y ago
    I get most of what you are saying, except you say that Python tuples must be able to resize. Python tuples can't resize, they are immutable. Lists are over-allocated to help with append operations, but tuples are not, because they have no append operation.
    • colanderman 10y ago
      Yes, you are right about that. Edited.