Port of the collections module

As multiple people have expressed an interest in porting the CPython collections module to Transcrypt, this issue has been openened to discuss its design.

My five cents, for a start:

With a module like collections, speed and efficient memory use is important.
So while the API should match the API of the CPython module as much as possible,
probably on the inside in some places native JS should be used.

What I'd like to avoid is encapsulation of overly large general purpose JS libraries with a lot of fat in them, since Transcrypt apps claim to result in fast pageloads.

My proposal is to make it work starting with JS 6, so to drop JS 5 compatibility for this module. (The closure compiler can always generate a polyfill). In this way certain optimizations of JS6 (like e.g. for...of) can be used to get the best performance.

In general compactness and speed is an important design goal for Transcrypt modules, sometimes at the expense of that last few percent of CPython compatibility, although I'd like to avoid that as much as possible.

One other thing to reckon with, is compatibility of Transcrypt datastructures with JS libraries, although that plays only a limited role in this case.

@JdeH

@JdeH sounds reasonable to me. Would it be wise to start with a pure Python implementation and selectively swap out parts for an ES6 implementation after profiling it?

A couple of other things I wondered about:

The CPython implementation relies on weakrefs for some of the collection types. Since there's no notion of weakrefs in JS, I wasn't sure if that was something that needed to be considered.
In general, how do you start on porting a module like this? Is the PyPy implementation a good place to start?

I'll try to answer your questions as thoroughly as possible, but the answers I give are not absolute. It will take some figuring out to find the ideal route.

In general with optimizations it is the case that one can best start out simple, to get a clean design, and then only optimize the bottlenecks. So that would be an argument in favor of starting with a pure Python implementation and then optimizing some parts directly in JS.
On the other hand some datastructures in Transcrypt currently are implemented with JS lib compatibility in mind, like e.g. dict, that's in fact a pure JS object. However JS6 has some new datatypes like Set and Map, that may be suitable as a basis for some types in the collections module, or it may not, I have no definitive opinion on that, it's just something that requires careful consideration.
With regard to the weakref's: Indeed in JS we'll have to do without them. This means that certain references have to be destroyed explicitly (or 'cyclic' refs prevented), since otherways objects will be kept alive for no reason and memoryleaks will result.
With regard to PyPy: While inspiration may be found here, the PyPy implementation uses e.g. the threads module that isn't available in Transcrypt because of browser limitations. So I don't know if it will help much.

Maybe it's good to also look at some pure JS implementations, e.g. of a deque, as they may be quite efficient.

In general I expect that designing something like this will require some trial and error, refactoring and backtracking. Once it's there I expect it to be heavily used, so it pays of if indeed it's efficient.

Yet another point of consideration (though a dull subject) is licensing. The license of whatever code is borrowed from, should be compatible with Apache 2. MIT is, LGPL may be, GPL certainly isn't. The most important point is that Transcrypt is also allowed to be used in commercial closed source projects. One isn't obligated to publicize any sourcecode. Any 3rd party code used should grant the same freedom.

In general: If you embark on this (not any obligation), take your time. There's no hurry, quality is preferred over quantity here. And it really would be a very useful contributing that's going to benefit many!

@JdeH

Thanks @JdeH! I'm interested in contributing. My approach will probably be to try and implement one of the collection types to start with, and I'll open a PR to get some early-stage feedback on the general approach. I hope to make a start this week.

@harto

@harto Looking forward to your PR

@JdeH

In my fork I made OrderedDict, @JdeH what do you think about implementation?

@neriusmika

I've studied your OrderedDict implementation and I see that it's based on bare JavaScript objects, just as is the ordinary dict.

This approach was choosen for dict because I wanted it to be compatible with JSON literals, to be able to seamlessly use JS libraries. This led to limitations like keys always having to be strings, since actually they are names of attributes. To be able to use numerical keys, whenever a string key can be interpreted as a number, it is indeed interpreted as such. While this approach isn't ideal, it was the only way to get good interoperability with JavaScipt libraries.

With OrdereredDict there may be a somewhat different approach that gets us closer to CPython behaviour without sacrificing performance:

Since there are no JSON-like OrderedDict literals of the form {key1: value1, key2: value2 ...} the JSON compatibility doesn't play a role here. In other words, there's no compelling reason for OrderedDicts to be JS objects, even though I think it's good that in your code OrderedDict has Dict as a conceptual (rather than real) ancestor class.
Another development is that Ecmascript 6 officially supports the Map datatype. It doesn't have the restriction of requiring string keys, so a true distinction can be made between 3 and '3' as key. Moreover the docs of Map say:

A Map object iterates its elements in insertion order
So a Map is very similar to a Python orderedDict, without the need to maintain a parallel ordered datastructure in the form of a list (which may be expensive with very large OrderedDicts holding very small objects, e.g. only references).

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map

And taken from that site:

Objects are similar to Maps in that both let you set keys to values, retrieve those values, delete keys, and detect whether something is stored at a key. Because of this (and because there were no built-in alternatives), Objects have been used as Maps historically; however, there are important differences that make using a Map preferable in certain cases:

The keys of an Object are Strings and Symbols, whereas they can be any value for a Map, including functions, objects, and any primitive.

You can get the size of a Map easily with the size property, while the number of properties in an Object must be determined manually.

A Map is an iterable and can thus be directly iterated, whereas iterating over an Object requires obtaining its keys in some fashion and iterating over them.

An Object has a prototype, so there are default keys in the map that could collide with your keys if you're not careful. As of ES5 this can be bypassed by using map = Object.create(null), but this is seldom done.

A Map may perform better in scenarios involving frequent addition and removal of key pairs.

Because of the points above, Map seems the ideal candidate as basis for an OrderedDict.
Extra "Python-style" methods could be added to it just the way you do that rightnow.
So it seems much of your code could be retained, but we'd have a real dict with typed keys rather than strings that are sometimes cleverly interpreted as numbers.

Since Transcrypt uses Google Closure, the minified result would still run on JS5.

In my opiniion it's worth while to benefit from the parallel between JS Map and Python OrderedDict.
What do you think?

By the way I expect more of this to happen in the future. Once JS has comprehensions and sets, the Transcypt implementations of these would become much simpler.

This may already be the case with destructuring assignments, but I do not yet fully trust JS on that point...

I looked at Map type, but as I know, it doesn't support index like assignment like a['b'] = 5, it has methods get, set, so how can we predict at compile time, that object is OrderedDict and convert to a.set('b', 5) ?

But actually with Proxy I think it can be made. Still we can't use it with ES5, because there is no fully functional polyfill for proxies and never be. To make collections work with ES5 is almost impossible, without rewriting compiler and slowing down all the other types.

Bedankt. But actually I found some problems with jscall approach, not everywhere it can be applied. The shitty javascript "this" scope problem. Sometimes "this" is passed as null, later I'll try to make a test.

@JdeH

@JdeH, probably there is no any easy solution to this problem. I think we must leave only jscall pragma without global switch, because it would be to dangerous. And use that pragma on specific methods where performance is important. There is no need to fix decorators for them too. Even simple transcrypt dictionaries have this problem with "this":

d1 = {'a': 'A', 'b': 'B'}
d2 = {'c': 'C', 'd': 'D'}
update = d2.update
update(d1)  <== TypeError: Cannot set property 'a' of undefined

OK, no problem at all.
It's nice that we have this optimization where it really counts.
And quite some warning words about its limitations should be in the docs.

I will take the global switch out again (currently a bit thinly spread).
It would be no good anyhow, making bound pointer assignment impossible.

However the possibilty to write a fast container in Python as part of a possibly heavily used lib is a big win.

Come to think of it, the impact of an eventual global switch can be limited by starting modules that would have problems with __pragma__ ('nojscall'). I'd like to know a little bit more of exactly what the limitations are before throwing out the switch. Will try to find some time for that. But if the switch remains it should be accompanied by a big fat warning.

Yes, I have tested on my code, when you carefully select which methods to optimize, then there are no problems.

This is awesome! I'm just getting started with defaultdict, which I think should be relatively simple. I'll be sure to report progress in here, so we can coordinate efforts.

@neriusmika out of interest, what does the __bases__ assignment in OrderedDict accomplish?

class OrderedDict:
    __bases__ = [dict]

@harto

@harto, because we can't inherit from dict type, without this line OrderedDict will show that it's inherited from "object", so functions like isinstance, issubclass will behave differently comparing to cpython. Actually I don't remember exactly, but I think that OrderedDict is inherited from dict :)

P.S. as Jacques said, it's some genetic engineering :)

Got it! And is the reason we can't inherit from dict because it's implemented in JS? Or because OrderedDict doesn't need to inherit dict's implementation (because it uses Map internally)?

It's because Transcrypt dict is just augmented js object. Implementation is different from standard classes and it's impossible to inherit from dict. That's why we need to make these classes from scratch.

I had some free time this evening to spend on defaultdict.

My understanding is that if I implemented it as a Python class, users would need to use opov to be able to do dict lookups. I don't know if that's expected or desirable. If not, it occurred to me that we might be able to use a JS Proxy to get the desired behaviour. Let me know if you have any thoughts about this.

@harto

@harto: I know @neriusmika has met this dilemma in working on the OrderedDict class, so he's probably in the best position to answer this. I remember he has tried JS Proxy and we discussed the pro's and con's.

@neriusmika: I should again dive into this, but currently I don't remember exactly what were the considerations. I know you started out with JS / JS Proxy. I don't see the opov pragma in your committed autotest code but I do see __setitem__ etc. in the collections code. Could you clarify to @harto (and refresh my memory on this)? It's probably somewhere halfway completion, as I had to deactivate the collection tests in the master branch, e.g.

# __pragma__ ('ifdef', 'undefined__esv6__')
if 'undefined__esv6__' in __symbols__:
    import module_collections
# __pragma__ ('endif')

KR
J

Jacques, there are some problems and now I can't decide which way to go.

Using python source with proxies:

bad performance (of course we need to decide what is acceptable performance, but it's slower than pure js objects, like current dict implementation).
does not support non string keys (Proxies limitation).

Using pure js implementation:

impossible to inherit from such pseudo classes.
does not support non string keys.
good performance.

The third possibility is to make with python classes and operator overloading, but every access to items must be overloaded, so again:

extra call would slowdown performance.
higher probability of mistakes.
support any type as keys (with internal Map).

P.S. __setitem__ in my implementation is the method called by proxy handler.

@harto

@harto: This sums it up nicely. By interpreting each string that denotes a number as a numerical key we can have numerical keys, just as with the "normal" sets/objects. It covers the majority of cases.

@neriusmika: I know you know this, but I mention it to clarify for @harto.

@harto @neriusmika
For collection classes both time and space performance are important, although I slightly favor time performance. We absolutely need to keep up with JavaScript on that point, to offer an uncompromising alternative. Speed and compactness are the niche and unique selling point of Transcrypt, making it truly usable for professional applications.

If that requires pure JS I am fine with it. But in that case I think it's important to share as much code as possible between the diverse collection classes in the collections module. So if you both work on it it would require cooperation.

Some detail: Even in a pure JS implementation of e.g. an OrderedDict, it would be necessary to keep a list in parallel to maintain the ordering. That would hurt performance at storage time, so it's important to know if this is indeed (much) better than operator overloading.

Trying to reach some type of conclusion:

If overall performance by choosing possibility 2 is degraded more than 30% in choosing solution 3 over solution 2, I'd say lets pick 2.

If not, lets pick 3, but with as little code duplication between the collection classes as possible.

So we'd need a benchmark. I propose to do as many individual insertions as retrievals, using [].
Because both are potential performance bottlenecks, intuitively to equal degree.

Thoughts?

Just wanted in to resurrect this. Can someone summarize the current problems that we're facing? My vote is to just use Map. The important thing is that the code works, not that it's Javascript-like. Map fits closest to the Python datastructure: it's ordered. The only drawback is the .set and .get problem? Is that an issue? If the Python datastructure is a dictionary, generate a Map and always use set and get?

I'm just not sure of where the hold up is. Why is "index like assignment" an issue? Technically if what you need is what a Map does you should be using a map, and .set and .get and not index-like-assignment.

Indeed this has come to a standstill.
Currently I'm quite tied up in getting 3.7 out and other participants seem to have similar considerations.

Summarizing:

It would be very useful to have a collections module with (as much as possible) the same API as the one that comes with CPython 3.7
Performance (native JS-like speed and compact storage) is very important for this module, since it will probably be intensively used for large in-memory data structures.
In my view JS5 compatibility can be dropped (and, if needed, achieved with the usual polyfills).
The JS Map type is probably most suitable as a basis for the OrderedDict class that's part of the collections module.
As Python OrderedDict support [] (index like assignment), Transcrypt OrderedDict should as well. This is not without (performance) problems, as can be seen from the above discussion.
Implementing ANY dict as a Map isn't an option, since Transcrypt (Python) dict literals like {1, 2, '4', [10, 20], True} should translate to plain JS objects to remain compatible with the countles JS libs that use object literals (JSON) as a way to initialize c.q. configure diverse library objects. So while OrderedDict probably should be based on Map, dict should not.
To achieve code compactness, code could be shared between similar data structures, although speed and data compactness are more important.

The current holdup, to be exact, is making an evidence (benchmark) based choice from the possibilities summed up at:

#442 (comment)

I propose to use the criteria described in:

#442 (comment)

Guess that sums if up.
If you or anyone else would have available the time and skills to get this going again, it would be much appreciated.
Whatever is chosen will greatly influence performance of Transcrypt applications, so it's important to do "the right thing". Which isn't easy and probably the reason this got stuck for so long...

One concluding remark: Transcrypt 3.7 will support JS modules (Python modules will translate to JS modules). This shouldn't have much (if any) influence on design of the collections module. It will be mainly a matter of merging. However it may be worth consideration to test it on the modules branch as well, although this is still a work in progress.

Implementing ANY dict as a Map isn't an option, since Transcrypt (Python) dict literals like {1, 2, '4', [10, 20], True} should translate to plain JS objects to remain compatible with the countles JS libs that use object literals (JSON) as a way to initialize c.q. configure diverse library objects. So while OrderedDict probably should be based on Map, dict should not.

I am not following on this point? As far as I can see, the concern here is that we need to provide a constructor that builds Maps from Objects for integration into libraries that Transcrypt generates. The reality is that the Object in Javascript is a poor fit for what even Javascript programmers use it for, those should all be Maps (with very few exceptions). That Object-literal notation doesn't create Maps is a huge design-flaw in JavaScript only because it makes it easy to do the wrong thing. But, we shouldn't be putting in more work to do the wrong thing for third party libraries. If we're generating code that does what the Python code does and uses Maps internally, that's great. I'm confused at why we're holding up a direct implementation on Map. We can perhaps provide convenience here, but it seems like our stance should be

Map is the JavaScript analog of a Python dict
JavaScript libraries should use Map instead

I definitely would like to see this done. I have a huge project that I think is mostly held up by this. I just want to be sure I'm on the same page and not stepping on toes or going against the grain. Then I'll dive in. BTW really cool project, I'm trying real hard not to go all fan boy on the issue tracker

Navigation Menu

Repository navigation

Port of the collections module #442

63 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Port of the collections module #442

Description

Activity

JdeH commented on Jan 14, 2018

harto commented on Jan 14, 2018

JdeH commented on Jan 15, 2018

harto commented on Jan 17, 2018

JdeH commented on Jan 17, 2018

nmrtv commented on Jan 24, 2018

JdeH commented on Jan 24, 2018

nmrtv commented on Jan 24, 2018

nmrtv commented on Jan 24, 2018

63 remaining items

nmrtv commented on Jan 26, 2018

nmrtv commented on Jan 26, 2018

JdeH commented on Jan 26, 2018

nmrtv commented on Jan 26, 2018

harto commented on Jan 26, 2018

nmrtv commented on Jan 26, 2018

harto commented on Jan 26, 2018

nmrtv commented on Jan 26, 2018

harto commented on Feb 13, 2018

JdeH commented on Feb 13, 2018

nmrtv commented on Feb 13, 2018

JdeH commented on Feb 13, 2018

EvanCarroll commented on Aug 21, 2018

JdeH commented on Aug 22, 2018

EvanCarroll commented on Aug 23, 2018

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions