5 ms·

Since PHP arrays are within a factor of two for the theoretical optimum for a dynamically typed language that unifies arrays and hashes, all these languages (ad

by fhars 15y ago

Since PHP arrays are within a factor of two for the theoretical optimum for a dynamically typed language that unifies arrays and hashes, all these languages (add javascript to the list) should have roughly comparable behaviour unless they do some ugly special casing for hashes where all keys are integers. [edit: see the comment by InfernalH for a measurement that indicates that ruby seems to do this.] You have to look that up in the relevant documentatio and/or source code. Perl on the other hand should fare better, as it distinguishes arrays and hahes. If you want performance, use a real programming language.

ars 15y ago
Javascript also distinguishes arrays and hashmaps.
ootachi 15y ago
JavaScript engines have many types of arrays. They do indeed resort to "ugly special casing" for objects in which all keys are integers: for instance, SpiderMonkey calls them "dense arrays". V8 has a similar optimization. Likewise, Lua stores a hashtable part and an array part for all objects. V8 and SpiderMonkey have optimizations for the values, too. When a value is a 31-bit integer (in the case of V8) or any number (in the case of SpiderMonkey), the value itself is optimized to avoid heap allocation. In V8's case optimized values take 32 bits, while in SpiderMonkey's case optimized values take 64 bits. So an array consisting of 100,000 integers will take 400K plus a negligible amount of malloc/GC slop in V8 and 800K in SpiderMonkey. JavaScript also has typed arrays, which allow the programmer to use fine-grained, optimized array buffers. Performing this experiment with a typed array will yield a 400K buffer in all engines that support the feature.
samdk 15y ago
Python and Ruby both have separate arrays and hashes. They're completely different data structures in both cases. Python's dict type is a hash table like you'd expect. Python's list is a pointer-array-backed list. (it may inline ints/similar things--I don't remember if CPython does, and exact details are implementation-dependent), and raw arrays are in the standard library if you need them. From a very quick check, a list of 100k ints in CPython is ~1.5mb, and a dict of 100k ints -> other ints is ~6mb. Ruby's hash and array implementations are similar, I think, although I don't know Ruby as well, so I don't know the specifics.
- jeltz 15y ago
  Good info about Python, but you are incorrect about Ruby. Hashes and arrays are totally different in the Ruby implementations I know of. EDIT: Sorry, I misread you. Ruby MRI and CPython are indeed similar. At least in Ruby MRI (the mainline) arrays are implemented as a struct with a size and a pointer to a normal C array which contains the object references (references in MRI are pointers to object structs which use the lower bits to inline integers of <= 31 or 63 bits, true, false, nil and symbols). Hashes in MRI I have not looked that much into but I believe they are a hash tables which in ruby 1.9 retain insertion order using pointers like a singly linked list.
  - masklinn 15y ago
    > Good info about Python, but you are incorrect about Ruby. Hashes and arrays are totally different in the Ruby implementations I know of. From its context, I'm guessing samdk is saying: > Ruby's hash and array implementations are similar [to Python's dict and list] not that they're similar to one another, which would make absolutely no sense considering his comment starts with: > Python and Ruby both have separate arrays and hashes. so I'd say you agree with him and misread his comment.
- scotty79 15y ago
  Does python have standard implementation of odict already? It's nice that Python and Ruby have data structures that trade some features for some memory and/or performance gain.
  - masklinn 15y ago
    > Does python have standard implementation of odict already? Yeppers, since 2.7/3.1: http://docs.python.org/library/collections.html#collections.OrderedDict http://docs.python.org/library/collections.html#collections.... http://docs.python.org/py3k/library/collections.html#collections.OrderedDict http://docs.python.org/py3k/library/collections.html#collect...
fauigerzigerk 15y ago
As I see it, doing the ugly special casing for you is exactly what any competent dynamic language implementation should do.
- maratd 15y ago
  Ugly special casing requires code that would detect those special cases. This adds overhead in terms of processing cycles and code. Most arrays, majority of the time, store a tiny amount of information. Less than a dozen entries. Doing that sort of detection is massive overkill and would actually hurt performance. You want to speed things up for the real world. Not artificial benchmarks. How many times in your code are you really going to need 100,000 integers in memory? Probably once in your entire lifetime, if that.
  - fauigerzigerk 15y ago
    I use much larger integer arrays all the time but that's beside the point. The question is whether or not it makes sense to make dynamic language runtimes as efficient as possible. I think it does, not because it necessarily helps all or even most existing programs, but because it enables people to create a much wider range of software with a language they already know. Many modern websites wouldn't be possible with JavaScript engines from 1999. And if you optimize at all, memory usage must be a top priority. Lack of memory is a lot more costly in terms of performance than a couple of C based heuristic checks. Creating and then garbage collecting an array full of individual integer objects doesn't just use a lot more memory, it's also orders of magnitude slower. The array doesn't have to be very large for that to matter as there may be large numbers of arrays.

by fhars 15y ago

ars 15y ago

Javascript also distinguishes arrays and hashmaps.

ootachi 15y ago

JavaScript engines have many types of arrays. They do indeed resort to "ugly special casing" for objects in which all keys are integers: for instance, SpiderMonkey calls them "dense arrays". V8 has a similar optimization. Likewise, Lua stores a hashtable part and an array part for all objects. V8 and SpiderMonkey have optimizations for the values, too. When a value is a 31-bit integer (in the case of V8) or any number (in the case of SpiderMonkey), the value itself is optimized to avoid heap allocation. In V8's case optimized values take 32 bits, while in SpiderMonkey's case optimized values take 64 bits. So an array consisting of 100,000 integers will take 400K plus a negligible amount of malloc/GC slop in V8 and 800K in SpiderMonkey. JavaScript also has typed arrays, which allow the programmer to use fine-grained, optimized array buffers. Performing this experiment with a typed array will yield a 400K buffer in all engines that support the feature.

samdk 15y ago

Python and Ruby both have separate arrays and hashes. They're completely different data structures in both cases. Python's dict type is a hash table like you'd expect. Python's list is a pointer-array-backed list. (it may inline ints/similar things--I don't remember if CPython does, and exact details are implementation-dependent), and raw arrays are in the standard library if you need them. From a very quick check, a list of 100k ints in CPython is ~1.5mb, and a dict of 100k ints -> other ints is ~6mb. Ruby's hash and array implementations are similar, I think, although I don't know Ruby as well, so I don't know the specifics.

jeltz 15y ago
Good info about Python, but you are incorrect about Ruby. Hashes and arrays are totally different in the Ruby implementations I know of. EDIT: Sorry, I misread you. Ruby MRI and CPython are indeed similar. At least in Ruby MRI (the mainline) arrays are implemented as a struct with a size and a pointer to a normal C array which contains the object references (references in MRI are pointers to object structs which use the lower bits to inline integers of <= 31 or 63 bits, true, false, nil and symbols). Hashes in MRI I have not looked that much into but I believe they are a hash tables which in ruby 1.9 retain insertion order using pointers like a singly linked list.
- masklinn 15y ago
  > Good info about Python, but you are incorrect about Ruby. Hashes and arrays are totally different in the Ruby implementations I know of. From its context, I'm guessing samdk is saying: > Ruby's hash and array implementations are similar [to Python's dict and list] not that they're similar to one another, which would make absolutely no sense considering his comment starts with: > Python and Ruby both have separate arrays and hashes. so I'd say you agree with him and misread his comment.
scotty79 15y ago
Does python have standard implementation of odict already? It's nice that Python and Ruby have data structures that trade some features for some memory and/or performance gain.
- masklinn 15y ago
  > Does python have standard implementation of odict already? Yeppers, since 2.7/3.1: http://docs.python.org/library/collections.html#collections.OrderedDict http://docs.python.org/library/collections.html#collections.... http://docs.python.org/py3k/library/collections.html#collections.OrderedDict http://docs.python.org/py3k/library/collections.html#collect...

fauigerzigerk 15y ago

As I see it, doing the ugly special casing for you is exactly what any competent dynamic language implementation should do.

maratd 15y ago
Ugly special casing requires code that would detect those special cases. This adds overhead in terms of processing cycles and code. Most arrays, majority of the time, store a tiny amount of information. Less than a dozen entries. Doing that sort of detection is massive overkill and would actually hurt performance. You want to speed things up for the real world. Not artificial benchmarks. How many times in your code are you really going to need 100,000 integers in memory? Probably once in your entire lifetime, if that.
- fauigerzigerk 15y ago
  I use much larger integer arrays all the time but that's beside the point. The question is whether or not it makes sense to make dynamic language runtimes as efficient as possible. I think it does, not because it necessarily helps all or even most existing programs, but because it enables people to create a much wider range of software with a language they already know. Many modern websites wouldn't be possible with JavaScript engines from 1999. And if you optimize at all, memory usage must be a top priority. Lack of memory is a lot more costly in terms of performance than a couple of C based heuristic checks. Creating and then garbage collecting an array full of individual integer objects doesn't just use a lot more memory, it's also orders of magnitude slower. The array doesn't have to be very large for that to matter as there may be large numbers of arrays.