Comment by samsquire | Hacker News Reader

Comment by samsquire | Hacker News Reader

Parent Full thread

Imagine you could interact with an object that had the API of all data structures. And it looked like a HashMap if you ran hash operations on it or like a linked list if you interacted with it that approach.

Behind the scenes the compiler shall analyse all your calls to that data structure and see what APIs you use to interact with it.

It can then decide which algorithms to use to optimise your interaction with that data structure.

If only computers could do hot/cold analysis. It could detect that you call a hash lookup in a hot for loop but only call the ordered map iterator from the admin screen and outside a loop.

I would then JIT compile the right data structure algorithm used from a bucket of implemented algorithms. So the data is kept optimised for its usage patterns.

Decisions such as use tombstones, compaction, vacuum, LSM trees, btrees, ordered, unordered, LSM trees with separate value storage, a growable array, a std::list or vector. All depend on what your intended access patterns to the data is.

Could also do clever materialized views. If you only use one view of the data rarely, it isn't efficient to maintain that view.

PHP's arrays are a bit like this. You can treat them either like an (ordered) hashmap or like a growable array. The underlying representation will adapt depending on whether the current state can be represented as an array.

And I hate it! I'm always unsure about an array's contents. I write functions that expect to operate on linear arrays and might misbehave if given a map, or vice versa. It's rare for the conflation to be helpful. Arrays and maps have different meanings and are used in different ways.

Maybe a very mild version of this would be helpful, like automatically converting an array to an array-backed deque—though even that case seems better handled by a linter making the suggestion, so the programmer can make an informed decision.

Going all the way would be terrible. Types are helpful. Even in a dynamically typed language they give you a vocabulary.

This sounds cool but currently compilers are very very bad at way way easier transformations

This is exactly how JavaScript arrays work.

I'm not convinced it's a good idea in general because usually the author will have a good idea about how the data will be accessed and what kind of data there is so if you can choose up front you may as well.

Plus having runtime analysis like that can lead to weird and unpredictable performance characteristics.

Reply on news.ycombinator.com