Dictionary Support #1053
Replies: 5 comments 30 replies
-
|
Dictionaries will also require a clear type annotation. Should we wish to support statements such as: then the initial declaration may also need an annotation |
Beta Was this translation helpful? Give feedback.
-
|
I think it is useful if only because it is one of the most basic Python objects. Most users learn about dictionaries before thy learn about |
Beta Was this translation helpful? Give feedback.
-
|
It is going to be very complicated to declare nested dictionaries, which is something that is commonly used. In my opinion we should think of dictionaries as containers to which |
Beta Was this translation helpful? Give feedback.
-
|
I agree. The only restriction that I would impose would be that all the keys should have the same type and all the values should have the same type. Originally when I wrote this comment I was thinking about the code : which does not provide enough information for Pyccel to deduce the type of the dictionary (including the type of the keys and values). However as mentioned above it is maybe not a problem as the dictionary cannot be accessed until something is added anyway |
Beta Was this translation helpful? Give feedback.
-
Sounds good to me. That appears to be the same assumption used by Numba: https://numba.pydata.org/numba-doc/dev/reference/pysupported.html#typed-dict |
Beta Was this translation helpful? Give feedback.
-
|
This should be doable with type annotations. See https://mypy.readthedocs.io/en/stable/cheat_sheet_py3.html#useful-built-in-types |
Beta Was this translation helpful? Give feedback.
-
|
Should we ever add C++ to Pyccel, a dictionary would be easily translated to a map |
Beta Was this translation helpful? Give feedback.
-
|
Hey same comment as in the list thread, see also https://github.com/P-p-H-d/c-stl-comparison#synthesis for additional C implementations. It would be great if you also supported sets. |
Beta Was this translation helpful? Give feedback.
-
|
It seems that maybe they have an unordered map but not an ordered map, so I guess it depends how close we want to stay to the Python implementation |
Beta Was this translation helpful? Give feedback.
-
|
They do have an ordered map too according to the readme. Anyhows ordered map (~std::map) is not a hash table and AFAIR python uses hash tables. |
Beta Was this translation helpful? Give feedback.
-
|
So Python since 3.6 uses hash tables that maintain key insertion order. This is something else than ordered maps using trees and ordering by key. Iteration with key insertion order seems to be quite uncommon. From a user perspective this particular property is not very critical. |
Beta Was this translation helpful? Give feedback.
-
|
Hello again,
Eliminating libs with copy-left licences and less support we still have:
PerformanceThe performance results from https://github.com/P-p-H-d/mlib/wiki/performance (written by the M*LIB devs) show:
*Tree means "Totally Sorted Tree": Red-Black Tree, AVL Tree, B-Tree or equivalent. Vector/List Code ExamplesM*LIB#include <stdio.h>
#include <gmp.h>
#include "m-array.h"
#define MPZ_OUT_STR(stream, x) mpz_out_str(stream, 0, x)
ARRAY_DEF(array_mpz, mpz_t, \
(INIT(mpz_init), INIT_SET(mpz_init_set), SET(mpz_set), CLEAR(mpz_clear), OUT_STR(MPZ_OUT_STR)))
int main(void) {
array_mpz_t a;
array_mpz_init(a);
mpz_t x;
mpz_init_set_ui(x, 16);
array_mpz_push_back (a, x);
mpz_set_ui(x, 45);
array_mpz_push_back (a, x);
mpz_clear(x);
printf ("ARRAY is: ");
array_mpz_out_str(stdout, a);
printf ("\n");
printf ("First element is: ");
mpz_out_str(stdout, 0, *array_mpz_get(a, 0));
printf ("\n");
array_mpz_clear(a);
}STC#define i_key int
#include "stc/cvec.h"
#include <stdio.h>
int main(void)
{
// Create a vector containing integers
cvec_int vec = {0};
// Add two integers to vector
cvec_int_push(&vec, 25);
cvec_int_push(&vec, 13);
// Append a set of numbers
c_forlist (i, int, {7, 5, 16, 8})
cvec_int_push(&vec, *i.ref);
printf("initial:");
c_foreach (k, cvec_int, vec) {
printf(" %d", *k.ref);
}
// Sort the vector
cvec_int_sort(&vec);
printf("\nsorted:");
c_foreach (k, cvec_int, vec) {
printf(" %d", *k.ref);
}
cvec_int_drop(&vec);
}CTL#include <stdio.h>
#define POD
#define T int
#include <ctl/vector.h>
int compare(int* a, int* b) { return *b < *a; }
int main(void)
{
vec_int a = vec_int_init();
vec_int_push_back(&a, 9);
vec_int_push_back(&a, 1);
vec_int_sort(&a, compare);
foreach(vec_int, &a, it)
printf("%d\n", *it.ref);
vec_int_free(&a);
}KLIB#include "kvec.h"
int main(void)
{
kvec_t(int) array;
kv_init(array);
for (j = 0; j < N; ++j)
kv_push(int, array, j);
kv_destroy(array);Other commentsI am not convinced that M*LIB has 3 dictionary types, depending on the complexity of the object being stored. This may add unnecessary complexity. KLIB includes a math library with pseudo-random generators. We will need to be careful to undefine macros to avoid problems later in the code. KLIB support for lists seems more limited (no sort function). STC allows contains an ND-array implementation (https://github.com/stclib/STC/blob/master/docs/cspan_api.md). It would be interesting to compare this to our implementation to see if we can find clues for #1129. If it is faster and we choose this library then we could directly replaced our implementation with this one. My PreferencesPersonally I find the M*LIB code harder to read than the others. It seems to be faster (according to their benchmarks) but not by much. I also think good docs are important and I'm wary of CTL having already been abandoned and reforked. My preference is therefore for STC. That said, I think any of these 4 would be valid solutions. What do you think @yguclu @adam-urbanczyk ? |
Beta Was this translation helpful? Give feedback.
-
|
Thanks for coming back to this. I don't have hands on experience here, but going by activity and stars I'd choose either M*LIB or STC. Out of those two STC has a nicer API and better docs. So +1 for STC. |
Beta Was this translation helpful? Give feedback.
-
|
See https://fortran-lang.org/packages/data-types/ for existing Fortran implementations. I like the look of https://github.com/SCM-NV/ftl as it seems to implement many objects (dict, list, etc) but would only add one dependency |
Beta Was this translation helpful? Give feedback.
-
|
It would be nice to be able to statically link without copy-left also for the fortran backend. |
Beta Was this translation helpful? Give feedback.
-
Considerations
|
Beta Was this translation helpful? Give feedback.
-
|
I have tried to summarise the options shown on fortran-lang.org. I know that the maintainers of this website are hoping that having an index of existing packages will help encourage the use of Fortran. So I think the list ought to be fairly complete (additionally there is https://github.com/fortran-lang/stdlib which I haven't mentioned as it is hard to work out what is supported currently (there are no user docs) but it has an MIT license so maybe this should be something to bear in mind for a future iteration). For me points 1 and 2 are the most important which is why I still like the look of FTL best. As regards licenses in order to avoid copyleft and use a maintained project, it seems we would have to implement our own solution. I think we should therefore do one (or both) of the following:
|
Beta Was this translation helpful? Give feedback.
-
|
Nice overview! |
Beta Was this translation helpful? Give feedback.
-
I would be more inclined to see this as a benefit. The C library is maintained which makes it much less worrying that
Actually this looks great. (As explained in their README) It seems very similar to FTL but with a more permissive license. I think this could be a good solution that would cover most of the cases we need for now |
Beta Was this translation helpful? Give feedback.
-
You are correct. FTL is released under LGPL license, not GPL as I wrote above. Therefore we can provide the user with a C Python extension which is dynamically linked to an FTL shared library. |
Beta Was this translation helpful? Give feedback.
-
|
I suppose we can compile an FTL shared library when we install Pyccel. This should only require a Fortran 2003 compiler. |
Beta Was this translation helpful? Give feedback.
-
|
We would have to double check the licences. From what I have seen there are often specific clauses about distributing the software |
Beta Was this translation helpful? Give feedback.
-
Dictionaries are very useful in python. Historically dictionaries were not supported due to sympy restrictions. As Pyccel is no longer constructed from sympy this is no longer a problem. Thus the only thing preventing implementation is the choice of how to implement it.
Personally I think the best solution would be to use an existing library however I have no experience with such libraries in Fortran or C.
From Google here are some options:
Fortran (see Fortran wiki)
C (see stack overflow)
Beta Was this translation helpful? Give feedback.
All reactions