PythonList implementation

[azouiten]

At the moment PythonList class does nothing except inherit from the PythonTuple class, we want to implement lists in Pyccel, we thought that we should at least try to implement heterogeneous lists. so far we thought of this implimentation:

#define DEFAULT_CAP 10

typedef enum e_type
{
    lst_bool     ,
    lst_int8     ,
    lst_int16    ,
    lst_int32    ,
    lst_int64    ,
    lst_float    ,
    lst_double   ,
    lst_cfloat   ,
    lst_cdouble  ,
    lst_list
};

typedef struct  s_elem
{
    void*       raw_data;
    enum e_type         type;
}               t_elem;

typedef struct  s_list
{
    t_elem**   elements;
    size_t  capacity;
    size_t  size;
}               t_list;

t_list   *allocate_list(size_t size);
t_list   *fill_list(t_list *list, ...);
void*    append(t_list* list_1, t_list* list_2);
void     clear(t_list* list);
t_list*  copy(t_list* list);
size_t   count(t_list* list);
void     extend(t_list* list, void* object);
size_t   index(t_list* list, void* value, int start, int stop);
void     insert(t_list* list, int index, void* object);
void*    pop(t_list* list, int index);
void     remove(t_list* list, void* value);
void     reverse(t_list* list);
void     sort(t_list* list, bool reverse);

@aihya @MostafaMamouni @EmilyBourne

[EmilyBourne]

cc: @yguclu

[EmilyBourne]

Do you think that you can avoid all need to know the type in advance (ie. while printing) via e_type? I think it would be good to benchmark some homogeneous examples with a homogeneous implementation and with an implementation like this to see what the cost of this is. Pyccel is designed for HPC usage, and in that context homogeneous lists are much more common. We shouldn't support more complicated things if it leads to significant slower code

[EmilyBourne]

Not knowing the type also prevents the compiler from making any related optimisations

[azouiten]

the way we thought about it is that there would be a list of supported types including classes, but I understand how this implementation would be costly computationally, especially if the list passed is homogeneous.

[EmilyBourne]

I don't understand how you can add classes to the supported types? Given that you don't know what user-defined classes will exist when you write the code for lists. For homogeneous lists, the class instance can be saved in a void* and accessed using the fact that it is homogeneous and therefore the type is known, but for heterogeneous lists you would need a way to expand e_type to handle new types (probably that would imply changing to an int, but then you need to keep track of which int refers to which class, without causing conflicts if you have files that call one another)

[EmilyBourne]

Am I right in saying that the proposed implementation could never handle a list containing class instances?

[azouiten]

we were thinking that it would be possible when the support for class is be added, as classes would just be another structure, that structure would be the supported type in lists and not the object itself.

[EmilyBourne]

I don't think that classes in general will be a structure. Rather I imagine a structure would be printed to represent each class. I'm not sure I see any reason to make them more complicated than that (apart from the fact that it would make what you are describing possible).

[EmilyBourne]

Don't forget that we want to support similar things in the different languages that we translate to. Fortran is a lot less flexible than C (that's one of the reasons why it's often faster), do you have any thoughts about whether it's possible to implement what you propose in Fortran?

[azouiten]

to be honest I have minimal experience with fortran so it was kinda neglected.

[EmilyBourne]

It would be great f you or someone else could do some research into this. At the moment the Fortran printer is still more advanced than the C printer (e.g. classes already have minimal support). It is also the default language and generates faster code, so it would be a shame to have to tell users to change language in order to use lists, especially if they use other things which are missing an implementation in C

[azouiten]

we will try to implement it in parallel with the C implementation.

[EmilyBourne]

Ok. There may be existing libraries for linked lists in Fortran that you can use

[EmilyBourne]

Have you thought about how you would implement functions such as abs ? E.g:

a = [1,2,3,4,5,6,7,8,9]
i = 0
while i < a.size:
    if a%2==0:
        a.pop(i)
    else:
        a[i] = abs(a[i])
        # long calculations using other functions that change depending on the type
        i += 1

Would this be translated to a while loop with a very large number of if blocks? What is the cost of this vs only allowing homogeneous lists?

[azouiten]

okay yes, I see the problem with heterogeneous list.
We could treat heterogeneous/homogeneous lists as different functionalities, but maybe that would just add to the complexity of the project without any significant advantage.

[EmilyBourne]

I'm not sure I see your point. Don't you have to shift the same number of items in both cases?

[EmilyBourne]

But if you have pointers to the objects then they are not necessarily contiguous in memory which could operations slower

[aihya]

You're right. void** was a leftover from the heterogeneous idea.

[aihya]

I don't know if I'm wrong but it looks like we recreate the same concept of nd_arrays, as they are homogeneous.

[aihya]

As @azouiten said, why not use nd_arrays and add support for list functions.

[aihya]

We have been considering another approach but we don't know if it might be better then implementing our own library. We came to the idea that we can use the cpython library and it's functions to create and manipulate the lists. For example, to create a list we can use PyList_New(some_size), and to pop or add an element to that list we can use PyList_Insert and other ones.
The big advantage we have here is the maintainability of the code as all major functionalities are going to be handled internally within the cpython funcions, and so the challenge I think would be in the conversion from cpython lists to pyccel's internal ndarrays.
@azouiten @EmilyBourne

[EmilyBourne]

Do you have an estimation of the overhead for this method? I would be worried that it is quite memory intensive and slow.
It would be great if you could do some benchmarks

Remember the aim of pyccel is to produce High Performance code not to become a python compiler

[aihya]

I tested the creation of a list(size=1000000), populate and sorted it:

#include <Python.h>
#include <stdio.h>

void func()
{
        PyObject *list;
        PyObject *obj;

        list = PyList_New(1000000);
        for (int i = 0; i < 1000000; i++)
        {
                obj = PyLong_FromLong(1000000 - i);
                PyList_SetItem(list, i, obj);
        }
        PyList_Sort(list);
        PyList_Reverse(list);
        Py_DECREF(list);
}

int main()
{
        Py_Initialize();
        for (int i = 0; i < 100; i++)
        {
                func();
        }
        return (0);
}

And these are the stats:

➜  pyccel git:(numpy.sign) ✗ /bin/time -v ./a.out
        Command being timed: "./a.out"
        User time (seconds): 3.63    <----
        System time (seconds): 1.04  <----
        Percent of CPU this job got: 99%
        Elapsed (wall clock) time (h:mm:ss or m:ss): 0:04.67
        Average shared text size (kbytes): 0
        Average unshared data size (kbytes): 0
        Average stack size (kbytes): 0
        Average total size (kbytes): 0
        Maximum resident set size (kbytes): 47760
        Average resident set size (kbytes): 0
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 764857
        Voluntary context switches: 1
        Involuntary context switches: 18
        Swaps: 0
        File system inputs: 0
        File system outputs: 0
        Socket messages sent: 0
        Socket messages received: 0
        Signals delivered: 0
        Page size (bytes): 4096
        Exit status: 0

(We don't have the stats for our own library yet.)

[EmilyBourne]

Great! This definitely needs a comparison point though. If you can find a basic implementation of a sorting algorithm online then that could provide a rough idea

[aihya]

Ok, the cpython idea is definitely not a good one. I tried a simple test for array allocation and population for both our lib and using cpython functions.

This is cpython code:

#include <Python.h>
#include <stdio.h>

void func()
{
	PyObject *list;
	PyObject *obj;

	list = PyList_New(1000000);
	for (int i = 0; i < 1000000; i++)
	{
		obj = PyLong_FromLong(1000000 - i);
		PyList_SetItem(list, i, obj);
	}
	Py_DECREF(list);
}

int main()
{
	Py_Initialize();
	for (int i = 0; i < 500; i++)
		func();
	return (0);
}

Time result: ./test 13.48s user 5.39s system 99% cpu 18.872 total

And this is the code with our lib:

#include <stdio.h>
#include "lists.h"

void func()
{
	t_list	*list;

	list = allocate_list(1000000, lst_int32, NULL);
	for (int32_t i = 0; i < 1000000; i++)
		((int32_t *)(list->elements))[i] = i;
	free_list(&list);
}

int main(int argc, char **argv)
{
	for (int i = 0; i < 500; i++)
	{
		func();
	}
	return (0);
}

Time result: ./test_lib 1.36s user 0.00s system 99% cpu 1.370 total

[adam-urbanczyk]

+1 on this in general. TBH homogeneous lists implemented as dynamic arrays would be more needed. For C there are quite a few libraries that could be used (see e.g. this overview), not sure about Fortran.

[EmilyBourne]

Hello, thanks for giving your opinion. We completely agree. Homogeneous dynamic arrays are the priority.

@yguclu I was going to pick up and complete PR #1192 when I get back from my holidays but maybe we should discuss if this is the right solution or whether we would be better picking an existing C implementation

[yguclu]

Is PR #1192 for the C printer only? The PR description does not say.

[EmilyBourne]

It is mostly for the C printer but it also adds the list functions to the semantic stage