Re: A pragmatic solution to using arrays in picolisp
I support the last idea about that isn't necessary to touch core language, and if someone needs array support, it could be implemented the same way as e.g. ext and ht libraries. Best regards, Mansur --- skipped --- I don't think it's necessary to add arrays to the core language however, given a sufficiently featured array library, picolisp's FFI interface can be used to provide a nice abstraction above it. This is similar to how numeric arrays are used in Python with the numpy package. Functions are provided to copy data into and out of arrays from lists, dictionaries, or files, and the actual operations on the arrays are carried out by a native C library (and often third party libraries like blas/lapack). The arrays themselves are just opaque pointers to corrected sized and memory ordered malloc'ed regions. --- skipped --- -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: A pragmatic solution to using arrays in picolisp
Arrays are very useful for numeric computing over linked lists. Contiguous blocks of linear memory are much more efficient, improving on numeric density, cache occupancy, and being able to take advantage of specific CPU vector instructions. For GPU based computing, contiguous arrays are essential and linked lists are useless, they must be scanned in linear time and no warp-level parallelization is possible. I don't think it's necessary to add arrays to the core language however, given a sufficiently featured array library, picolisp's FFI interface can be used to provide a nice abstraction above it. This is similar to how numeric arrays are used in Python with the numpy package. Functions are provided to copy data into and out of arrays from lists, dictionaries, or files, and the actual operations on the arrays are carried out by a native C library (and often third party libraries like blas/lapack). The arrays themselves are just opaque pointers to corrected sized and memory ordered malloc'ed regions. Googling 'C array library' returns many interesting hits. Judy arrays also look very interesting: http://judy.sourceforge.net/ -Michel On Tue, Feb 17, 2015 at 9:04 AM, Enrique Sánchez petenr...@gmail.com wrote: But if you have such a redundant structure, where the array elements point into the list, you have a large overhead to build both the array and the list. I think that building trees take more overhead than executing a malloc and building a linear list. (And probably more cons cells). You can't do any changes (cons, insert, delete, reverse) without rebuilding the array. And - as before - you have to keep track of your arrays to know when to dispose them. There's no point in creating array helpers for small lists elements. These helpers are only useful for large lists. Most of us always use these big arrays as global, static (in the C sense), created at the beginning of a program, living during the whole lifetime of a program, and being disposed of manually at the end of the program, or automatically by the system at program end. During their life, these arrays don't grow, the structure remains the same, because they have the nature of an array. Of course I could use the allocation and disposing of small arrays at many points in the source code with this system, as you fear, like C and C++ programmers do. But that is hell, I would not do that. They do that because they don't have other means. So the allocation and disposing using malloc() and free(), are only made typically for a pair of big arrays at two well known points in the source code, and that's it. The following is a typical program showing the use of array helpers: (setq *Ram (array (readFile 65536 ram.bin)) # memory array *PC0 # Program pointer *SP16384 # Stack pointer *Reg1 0 *Reg2 0 *Reg3 0 # general registers *Run T ) (while *Run (setq *P (nth: *Ram *PC)) # random access (execute *P) ) [... here would be all the main code ...] (dispose *Ram) # optional (bye) For this kind of program, using trees to emulate raw memory array functionality seems convoluted, and I guess at least 10 times slower. Convoluted because of the emulation of a more primitive structure by means of a more complex one. The most important data structure in Picolisp, the cons cell, is nothing more than a array element, addressable by a pointer, that is just an array index. If I want to use Picolisp to do exploratory programming of computer interpreters, then having arrays seems natural. I'm still not convinced at all that accessing list elements by a numeric index is really needed, or at least justifies the effort. The mentioned 'hash' mechanism is alread there, in constructs like the built-in 'cache' function (see also the answer by Denis Fourt). If you consider that for building interpreters, emulating raw memory indexes with trees is appropiate, then I don't think so. I see it half way as convoluted as clogging the symbol table with symbols like 'M1, 'M2 ... for doing that. Or may be you consider that trees are not appropiate for that kind of application, as is my opinion, and your solution is to resort to another computer language, as C, for doing that kind of programming. In this case I would understand your choice. I would like to be able to do that kind of low level programming in picolisp. The implementation effort would be about 20 lines of code. -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: A pragmatic solution to using arrays in picolisp
On Tue, Feb 17, 2015 at 2:30 AM, Denis Fourt denis.p...@hotmail.com wrote: If I may provide an advice, in Purely Functional Data Structures from Chris Okasaki (Cambridge University Press, 1998), you will find various data structures based on lists which come close to regular arrays in term of access performance. This might be what you are looking for. And if you do now want to start from the book, you may start with Okasaki's PhD Thesis: http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf -- If technology is your thing plan to die reading manuals --Gene Woolsey -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: A pragmatic solution to using arrays in picolisp
I've changed my mind. If we have a linear list for which we need fast access, we can do another thing: Instead of substituting the list with an array structure, we can keep the list and use an array as a helper of the original list. That means that instead of storing the elements of a linear list in the buckets of the array and getting rid of the list, we can store the cdr's of the list and keep the list. So we can get rid of the 'get: and 'set: functions, that are very rigid, and break the Lisp programming style, as you said, and have only a 'nth: accessor. This has two advantages: 1. First (the big advantage) is that we retain all the usual list functions at our disposal, restoring Lisp programming style. 2. The patch to the garbage collector gets simpler: for (int i=1; i=current; i++) # loop thru each array if (void **p=arrays[i]) # only if array hasn't been disposed of markAll(p[1]); # we only need to traverse the first bucket -- So, recapitulating we would have only 3 functions: (setq *Ram (array (need 131072 0))) (nth: *Ram 5) (dispose *Ram) This use of arrays as helpers associated with some lists, instead of substitutes of lists, makes arrays even more segregated from the core of the language. I think that makes them more acceptable. -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: A pragmatic solution to using arrays in picolisp
On 2015-02-15 02:29, Alex Gilding wrote: One cheap workaround for this would simply be to have a nogc function that temporarily disables the GC around a piece of code. If you're crunching data in arrays, you probably want to isolate that operation in its own little high-performance block anyway. I would add some code to the garbage collector, in order to keep the array items protected. -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
RE: A pragmatic solution to using arrays in picolisp
If I may provide an advice, in Purely Functional Data Structures from Chris Okasaki (Cambridge University Press, 1998), you will find various data structures based on lists which come close to regular arrays in term of access performance. This might be what you are looking for. A simplified ML syntax is used in this book (because ML uses static types), some parts are dedicated to performance analysis and there are some interesting suggestions hidden in some of the exercices, if I remember well. Regards, Denis From: petenr...@gmail.com To: picolisp@software-lab.de Subject: Re: A pragmatic solution to using arrays in picolisp Date: Mon, 16 Feb 2015 20:19:40 +0100 I've changed my mind. If we have a linear list for which we need fast access, we can do another thing: Instead of substituting the list with an array structure, we can keep the list and use an array as a helper of the original list. That means that instead of storing the elements of a linear list in the buckets of the array and getting rid of the list, we can store the cdr's of the list and keep the list. So we can get rid of the 'get: and 'set: functions, that are very rigid, and break the Lisp programming style, as you said, and have only a 'nth: accessor. This has two advantages: 1. First (the big advantage) is that we retain all the usual list functions at our disposal, restoring Lisp programming style. 2. The patch to the garbage collector gets simpler: for (int i=1; i=current; i++) # loop thru each array if (void **p=arrays[i]) # only if array hasn't been disposed of markAll(p[1]); # we only need to traverse the first bucket -- So, recapitulating we would have only 3 functions: (setq *Ram (array (need 131072 0))) (nth: *Ram 5) (dispose *Ram) This use of arrays as helpers associated with some lists, instead of substitutes of lists, makes arrays even more segregated from the core of the language. I think that makes them more acceptable. -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: A pragmatic solution to using arrays in picolisp
Hi Enrique, If we have a linear list for which we need fast access, we can do another thing: Instead of substituting the list with an array structure, we can keep the list and use an array as a helper of the original list. Do you think this is a good idea? OK, you have a list then, where you can access the elements by index. But if you have such a redundant structure, where the array elements point into the list, you have a large overhead to build both the array and the list. You can't do any changes (cons, insert, delete, reverse) without rebuilding the array. And - as before - you have to keep track of your arrays to know when to dispose them. I'm still not convinced at all that accessing list elements by a numeric index is really needed, or at least justifies the effort. The mentioned 'hash' mechanism is alread there, in constructs like the built-in 'cache' function (see also the answer by Denis Fourt). ♪♫ Alex -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: A pragmatic solution to using arrays in picolisp
thanks for your ideas and elaborations! thank you for having created picolisp Personally, I must say that I am against using arrays in PicoLisp, and wrote it up a few years ago in: http://picolisp.com/wiki/?arrayAbstinence Yes, I have read it. I agree more or less with it. Can you give me an example where you need a list with 65536 elements, in a Lisp program? Normally you would use some kind of tree to maintain larger data structures, and you example of using helper list does exactly that. If I had a 65536 elements array at my disposal, the first thing I would do is to couple it to the cute 'hash picolisp function (whose output is 1..65536) in order to have very good hash tables. (I could use binary trees instead, hash tables are simpler and a little faster, binary trees are more powerful). If one is interested in building virtual machines in picolisp, I think that one needs arrays, to emulate flat memory above all, but as well to execute the machine instructions efficiently by table dispatching. Besides this, technically your implementation looks good. It breaks the Lisp programming style though. You can't use the rich set of list-manipulation functions on arrays. To do anything interesting, you have to either fetch the whole array (or parts of it) into a list, or operate one by one by accessing individual elements. Very tedious. I use lists for most tasks, as usual, it's only at very selected places that I would reach for an array for random access. You have to take care of garbage collecting these arrays by yourself, i.e. to know when a given array is no longer needed. and this inconvenience alone destroys the possible advantage of an array. Given a function markAll(CELL*) that marks all cons-cells reachable from a given cell, we can just insert the following code in the garbage collector marking phase, so that the contents of all arrays can be protected from being sweeped. for (int i=1; i=current; i++) # thru each array if (void **p=arrays[i]) # only if array hasn't been disposed of for (int j=1; j=size(p); j++) # thru each bucket markAll(p[j]); These 4 lines of code (plus the creation and disposing code) are the price to pay (I think) for having arrays in picolisp. Enrique. -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: A pragmatic solution to using arrays in picolisp
Hi Enrique, thanks for your ideas and elaborations! Personally, I must say that I am against using arrays in PicoLisp, and wrote it up a few years ago in: http://picolisp.com/wiki/?arrayAbstinence Can you give me an example where you need a list with 65536 elements, in a Lisp program? Normally you would use some kind of tree to maintain larger data structures, and you example of using helper list does exactly that. Besides this, technically your implementation looks good. It breaks the Lisp programming style though. You can't use the rich set of list-manipulation functions on arrays. To do anything interesting, you have to either fetch the whole array (or parts of it) into a list, or operate one by one by accessing individual elements. Very tedious. You have to take care of garbage collecting these arrays by yourself, i.e. to know when a given array is no longer needed. and this inconvenience alone destroys the possible advantage of an array. In addition: 2) I suppose that the garbage collector would have to keep track of all those CELL pointers in the array, that are outside of the reach of Correct. Without that, you can store only short numbers (up to 60 bits) in such an array. Data of any other type (bignums, symbols or lists) will be thrown away by the garbage collector and your program will crash horribly ;) ♪♫ Alex -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
Re: A pragmatic solution to using arrays in picolisp
2) I suppose that the garbage collector would have to keep track of all those CELL pointers in the array, that are outside of the reach of the picolisp symbol table. That would be the price to pay, I think a smaller price than adding another datatype. One cheap workaround for this would simply be to have a nogc function that temporarily disables the GC around a piece of code. If you're crunching data in arrays, you probably want to isolate that operation in its own little high-performance block anyway.
