oldk1331 wrote: > > On 12/11/18 3:55 AM, Waldek Hebisch wrote: > > oldk1331 wrote: > >> > >> This patch changes the Rep of Tree from > >> Union(node:Record(value: S, args: List %),empty:"empty") > >> to > >> Record(val : S, args: List %) > >> and uses "NIL$Lisp" to represent empty tree. > >> > >> Before this patch, > >> > >> (1) -> tree [1,2,3] pretend SEX > >> > >> (1) (0 1 (0 2) (0 3)) > >> > >> And after: > >> > >> (1) -> tree [1,2,3] pretend SEX > >> > >> (1) (1 (2) (3)) > >> > >> So this patch can save some (maybe a third) memory. > > > > Sorry that I did not comment earlier: this kind of change is > > very dangerous. Namely, it can work quite nice in testing > > and then lead to error say 3 years later. The point is > > that there is correspondence between FriCAS types and > > Lisp representation. Part of this correspondence are > > known to Spad compiler and (via declarations) transmited to > > Lisp compiler. So Lisp compiler is told that effectively > > Record never is NIL. Breaking this can lead to nasty > > errors when valid optimization is breaking "working" code. > > What if we do not use Rep, but use rep/per to trick the > compiler? Then the compiler will not know about underlying > representation and give them declaration.
rep/per alone solves almost nothing. The main problem is in operations. You would need to add new set of primitives consistent with desired representation at Lisp level. For example, U32Vector is represented by Lisp array, but of specialized type. Declarations present in operations for U32Vector are invalid for other arrays and operations for other arrays would be invalid for U32Vector. So you can use different representation, provided that it is done in consistent way and down to level of primitives. > > I'm also writing a DoublyLinkedList Domain using: > Rep := Record(val : S, next : %, prev : %) > > If I change that Rep to > Union(node:Record(val : S, next : %, prev : %),empty:"empty") > > Then the code will not only be much slower but also be much > more verbose: > > You can no longer access the "next" and "prev" pointer directly, > you have to check for empty case every time. Well, one can do one of the following: - dully implement genric pattern (with checks for empty) - only implement non empty case _and_ do not make it an aggregate - use specialized representation with needed primitives > > Let me add that Spad compiler contained (I would have to check > > if it still contain) code to optimize unions in way you are > > trying to do, namely avoid wrapper and tags in case when > > Lisp types are disjoint. Activationg this code would > > give large memory savings for several important types. > > But it would also mean that we need make sure that > > optimization is used only when it is valid and that > > declarations in generated Lisp code match. There > > is also question of runtime performance: smaller > > memory use can give large speedups, but without declaration > > at Lisp level code must contain more checks. So > > there is delicate balance, small examples probably > > would be slower while large would gain. Anyway, when > > I looked at this my conclusion was that we do not > > have developement resources to go in this direction. > > Simply, we already have too many bugs to add optimizations > > which are likely to bring more bugs. > > > > Concerning Tree, it has little use, so bugs here have less > > impact. But by the same logic optimizing Tree adds little > > Well, by improving Tree, my next target is to improve BinaryTree, > which use Tree as Rep. Next, maybe Red-black tree, and use that > as Rep of Set. I think these are important data structures > and should be optimized. Well, Tree as a representaion of BinaryTree is already suboptimal. BinaryTree as a representation of balanced trees again adds overhead. If we want fast and efficient search tree we should use specialized representation. Note that given inheritance chain you propose empty set would be represented as empty tree, so disallowing empty tree would break inheritance at first place. Concerning Set it is not so clear for me what to do with representation. From point of view of memory use arrays are more efficient (OK, list of arrays would be most compact). For small sets lists are almost as good and for small sets using lists gives quite good speed with rather short code. In ordered case arrays could give comparable or better search speed compared to balanced trees, faster merge but slow insertion. More generaly, for many special cases specializing code and data structures could give us gains. Problem is that currently automatic specialization of data structures is inpractical and even explicit specialization by programmer has rather poor support (in a sense C++ has best known support for this, but IMO trying to emulate C++ here is not wise). So specialization brings cost of extra/duplicated code and growing complexity. Complexity means more bugs, possibly up to the point of program becoming unusable. In case of FriCAS the main theme was to have generic code and data structures, which are way slower and need more space than special purpose versions. But this generic code is supposed to be there ready to be used -- having slow code solving a problem is much better than having no code at all. In some cases generic code gives actually quite good performance (mainly when most work is done by specialized code in lower layers). In cases which get a lot of use we provide specialized versions. But this is done mostly based on measurements of real tasks. For example, work on guessing package showed that several basic routines were too slow (and we replaced them by faster versions). But one needs to be conservative here: in few cases what first looked as improvement turned out to be slower than existing code. Coming back to trees: I think that we need fast seach trees, but that they need separate representation, different from other trees. I have doubts about replacing representation of sets, for me it looks more resonable to use search trees directly or possibly via a separate domain say 'TreeBackedSet'. -- Waldek Hebisch -- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group. To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel+unsubscr...@googlegroups.com. To post to this group, send email to fricas-devel@googlegroups.com. Visit this group at https://groups.google.com/group/fricas-devel. For more options, visit https://groups.google.com/d/optout.