dict implementation

[ffao]

Well, somebody had to do this, so I gave it a try.
Here is a (tentative) dict implementation, I haven't tested it
extensively yet: http://stuffr.net/d/06il36z

There are some warnings about NULL arithmetic and lines 2217 and 2218
of builtin.cpp give errors (I probably deleted the declaration for
__none somewhere, I'm not sure). It does pass some preliminary tests
if you comment out those lines, if that counts for something (not the
shedskin unit tests however, as I couldn't figure out which ones deal
with dicts and which ones don't).

ffao

--
You received this message because you are subscribed to the Google Groups "shedskin-discuss" group.
To post to this group, send email to shedskin...@googlegroups.com.
To unsubscribe from this group, send email to shedskin-discu...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/shedskin-discuss?hl=en.

[Jérémie Roquet]

Hi,

2010/5/6 ffao <fet...@gmail.com>:

> Well, somebody had to do this, so I gave it a try.
> Here is a (tentative) dict implementation, I haven't tested it
> extensively yet: http://stuffr.net/d/06il36z

Thanks ffao!

> There are some warnings about NULL arithmetic and lines 2217 and 2218
> of builtin.cpp give errors (I probably deleted the declaration for
> __none somewhere, I'm not sure). It does pass some preliminary tests
> if you comment out those lines, if that counts for something (not the
> shedskin unit tests however, as I couldn't figure out which ones deal
> with dicts and which ones don't).

You just deleted the following lines:

template<class T> T __none() { return NULL; }
template<> int __none();
template<> double __none();

After re-adding them, it works fine in my tests :-)

Side note: there is something funny (or not) with shedskin's dict :
the storage (or display) order is not the same as with CPython.
For example:

foo = {
'bar': 'lol',
'xd' : 'pdtr',
'tt': 'vg',
'56': '33',
}

CPython: {'tt': 'vg', '56': '33', 'bar': 'lol', 'xd': 'pdtr'}
ShedSkin (old): {'bar': 'lol', 'tt': 'vg', '56': '33', 'xd': 'pdtr'}
ShedSkin (new): {'xd': 'pdtr', 'bar': 'lol', '56': '33', 'tt': 'vg'}

Best regards,

--
Jérémie

[Mark Dufour]

just a note to others that you're the author of the current set implementation in shedskin.. :-)

--
"Overdesigning is a SIN. It's the archetypal example of what I call 'bad taste'" - Linus Torvalds

[ffao]

For the NULL warning, my workaround was to add a new
"difference_found" variable: http://stuffr.net/d/5tgrb08
At least g++ is happy now!

> Side note: there is something funny (or not) with shedskin's dict :
> the storage (or display) order is not the same as with CPython.

Seeing as how display order is strictly dependant on hashes, and
shedskin's hashes are different from CPython's, I'm hardly
surprised. :)

ffao

[Mark Dufour]

Seeing as how display order is strictly dependant on hashes, and
shedskin's hashes are different from CPython's, I'm hardly
surprised. :)

 

the hashes are getting closer with every release. for example, I just took frozenset hashing from cpython. I'd really like them to be identical later on, if possible, and hide any incompatible optimization behind command-line options..

thanks,
mark.

--
"Overdesigning is a SIN. It's the archetypal example of what I call 'bad taste'" - Linus Torvalds

[Mark Dufour]

I'm afraid I don't have any time this weekend because of family matters, but perhaps someone else would be interested in doing some preliminary performance tests..? thomas, perhaps you'd like to see if this helps your it++/++it test case..?

btw, I haven't looked, but does the code avoid GC for integer dicts yet, the same way the set implementation does..? iirc, this one made a big difference for a very common use of sets.

thanks!
mark.

[ffao]

Well, the dict currently uses GC_MALLOC_ATOMIC for <int, int> dicts. Good thing you mentioned it though, as it was previously using atomic for <int, *> dicts, which is clearly not right...

By the way, I do realize I did exactly what I said I wouldn't do by coding this, but you can't blame me for getting excited about this again, can you? :)

ffao

[Mark Dufour]

alright, I finally had some time to test this! :D thanks again!

I committed your patch to SVN, after some minor fixes:

- items() didn't compile
- made get() use __none<> again
- fixed collections.defaultdict (inherits from dict!)
- readded __addtoitem__ ('some_dict[x] += blah')

after these fixes, all unit tests work again. there are still a few minor (performance and other) issues I will be looking into further in the week as time permits (for example dealing with the new __ss_int type), but in all it looks quite good! it's nice to see some things (EMPTY_TO_MINSIZE..) could be shared with the set implementation.

then hopefully within a few days as well, I will be able to run the euler test set again with this new implementation.. :D


thanks again,
mark.

--
"Overdesigning is a SIN. It's the archetypal example of what I call 'bad taste'" - Linus Torvalds

[Mark Dufour]

hiya,

so here are some useful performance improvements:

http://code.google.com/p/shedskin/source/detail?r=1445#

note that the change in myallocate (to use the new parameterized __ss_int type) should also help some of the non-dict euler tests, as I'm quite sure gc_malloc_atomic wasn't working in combination with shedskin -l..

I'll try to run the euler test set again tonight..


thanks again!!
mark.

[Mark Dufour]

good news after re-running the 22 euler tests today that psyco was faster on: shedskin now wins 5 of these, and has become significantly faster on 4 others:

euler12: 0.144 -> 0.122 seconds
euler47: 0.39 -> 0.24
euler72: 4.6 -> 3.0
euler74: 13.0 -> 11.44
euler98: 0.41 -> 0.28
euler114: 0.24 -> 0.21
euler124: 0.55 -> 0.27
euler179: 79 -> 66
euler260: 39.5 -> 31.2

I think most of these improvements come from the new dict implementation ^^

thanks again!
mark.

[ffao]

Oops, look like we/I forgot to implement __to_py__... I guess this
should do:

template<class K, class V> PyObject *dict<K, V>::__to_py__() {
PyObject *p = PyDict_New();
int pos = 0;
dictentry<K,V> *entry;
while (next(&pos, &entry)) {
PyDict_SetItem(p, __to_py(entry->key), __to_py(entry->value));
}
return p;
}

In set::__to_py__ you created a list then called PySet_New on it; if
there is a speed difference it would be profitable to do whatever is
faster on both...

[Mark Dufour]

template<class K, class V> PyObject *dict<K, V>::__to_py__() {
   PyObject *p = PyDict_New();
   int pos = 0;
   dictentry<K,V> *entry;
   while (next(&pos, &entry)) {
       PyDict_SetItem(p, __to_py(entry->key), __to_py(entry->value));
   }
   return p;
}

thanks! committed. I guess I should more regularly test extension module support, perhaps after each change..

mark.

--
"Overdesigning is a SIN. It's the archetypal example of what I call 'bad taste'" - Linus Torvalds