On 7 October 2017 at 21:29, oldk1331 <[email protected]> wrote:
> About the "Maybe Maybe X" problem:
>
> Since Waldek gives the idea of using GENSYM() to mark failure,
> I want to hear his opinion.
>
> One of my original motives to introduce Maybe is performance,
> the other motive is better abstraction. Seems we can't have both.
I think we can have both. Your inline optimization is all that is needed.
> If I have to choose between them, I'll choose better abstraction.
>
> If we choose "Rep := List R", then the performance should be
> same as Union(X, "failed").
>
With the current SPAD compiler and your most recent inline
optimizations that does not seem to be true. My benchmark below shows
that "Rep := List R" has almost the same performance for testing
failed and retracting/upwrapping a value as using global GENSYM.
Testing empty?/failed? is actually a little bit faster.
"Union(R,"failed")" on the other hand does seem to take about 80%
longer to unwrap a value.
> I did a simple benchmark on subtractIfCan$NNI, the GENSYM()
> approach can be 12% faster (or 20% faster if a GC happens).
> That may speed up "groebner" by 4%. I guess if such optimization
> is really needed, it can be done case by case.
>
I recommend that you try your simple benchmark again using "Rep :=
List R". You should get the same performance as with global GENSYM
(notwithstanding a possible increase in GC).
--
wspage@strix ~ $ fricas -nox
(1) -> )r maybe-bench-all
)co fricas-oldk/src/algebra/maybe.spad
Compiling FriCAS source code from file
/home/wspage/fricas-oldk/src/algebra/maybe.spad using old system
compiler.
MAYBE abbreviates domain Maybe
------------------------------------------------------------------------
Maybe is now explicitly exposed in frame frame1
Maybe will be automatically loaded when needed from
/home/wspage/MAYBE.NRLIB/MAYBE
)co maybe-bench-oldk
Compiling FriCAS source code from file
/home/wspage/maybe-bench-oldk.spad using old system compiler.
TESTM abbreviates package TestMaybe
------------------------------------------------------------------------
TestMaybe is now explicitly exposed in frame frame1
TestMaybe will be automatically loaded when needed from
/home/wspage/TESTM.NRLIB/TESTM
)set message type off
f1 1;
)time on
-- using Maybe(R) with Rep:=R and global GENSYM() to mark failure
-- testing failed?
f1 200;
Time: 0.47 (EV) = 0.47 sec
-- unwarp
g1 200;
Time: 0.39 (EV) = 0.39 sec
--
-- using Maybe(R) with Rep:=R and local GENSYM() to mark failure
-- testing failed2?
f2 200;
Time: 1.20 (EV) = 1.20 sec
--
-- using Union(R,"failed")
-- testing case "failed"
f3 200;
Time: 0.44 (EV) = 0.44 sec
-- coerce to R
g3 200;
Time: 0.00 (IN) + 0.70 (EV) + 0.00 (OT) = 0.71 sec
)time off
)co maybe.spad
Compiling FriCAS source code from file /home/wspage/maybe.spad using
old system compiler.
MAYBE abbreviates domain Maybe
------------------------------------------------------------------------
Maybe is already explicitly exposed in frame frame1
Maybe will be automatically loaded when needed from
/home/wspage/MAYBE.NRLIB/MAYBE
)co maybe-bench4
Compiling FriCAS source code from file
/home/wspage/maybe-bench4.spad using old system compiler.
TESTM4 abbreviates package TestMaybe4
------------------------------------------------------------------------
TestMaybe4 is now explicitly exposed in frame frame1
TestMaybe4 will be automatically loaded when needed from
/home/wspage/TESTM4.NRLIB/TESTM4
f4 1;
)time on
-- using Maybe(R) with Rep:=List R
-- testing empty?
f4 200;
Time: 0.38 (EV) = 0.38 sec
-- retract
g4 200;
Time: 0.43 (EV) = 0.43 sec
-- file: maybe-bench-all.input
)co fricas-oldk/src/algebra/maybe.spad
)co maybe-bench-oldk
)set message type off
f1 1;
)time on
-- using Maybe(R) with Rep:=R and global GENSYM() to mark failure
-- testing failed?
f1 200;
-- unwarp
g1 200;
--
-- using Maybe(R) with Rep:=R and local GENSYM() to mark failure
-- testing failed2?
f2 200;
--
-- using Union(R,"failed")
-- testing case "failed"
f3 200;
-- coerce to R
g3 200;
)time off
)co maybe.spad
)co maybe-bench4
f4 1;
)time on
-- using Maybe(R) with Rep:=List R
-- testing empty?
f4 200;
-- retract
g4 200;
--
-- file: maybe-bench-oldk.spad
--- Maybe benchmark package
)abbrev package TESTM TestMaybe
TestMaybe() : Exp == Imp where
Exp == with
f1 : Integer -> Integer
g1 : Integer -> Integer
f2 : Integer -> Integer
f3 : Integer -> Integer
g3 : Integer -> Integer
Imp == add
NNI ==> NonNegativeInteger
import from Vector NNI
v1 : Vector Maybe NNI := new(10^6, failed())
v2 : Vector Union(NNI, "failed") := new(10^6, "failed")
w1 : Vector Maybe NNI := [wrap i for i in 1..10^6]
w2 : Vector Union(NNI, "failed") := [i for i in 1..10^6]
f1 x ==
v := v1
for j in 1..x repeat
for i in 1..10^6 repeat
failed? qelt(v, i)
x
g1 x ==
w := w1
for j in 1..x repeat
for i in 1..10^6 repeat
unwrap! qelt(w, i)
x
f2 x ==
v := v1
for j in 1..x repeat
for i in 1..10^6 repeat
failed2? qelt(v, i)
x
f3 x ==
v := v2
for j in 1..x repeat
for i in 1..10^6 repeat
qelt(v, i) case "failed"
x
g3 x ==
w := w2
for j in 1..x repeat
for i in 1..10^6 repeat
qelt(w, i)::NNI
x
--
-- file: maybe-bench4.spad
--- Maybe benchmark package
)abbrev package TESTM4 TestMaybe4
TestMaybe4() : Exp == Imp where
Exp == with
f4 : Integer -> Integer
g4 : Integer -> Integer
Imp == add
NNI ==> NonNegativeInteger
import from Vector NNI
v4 : Vector Maybe NNI := new(10^6, empty())
w4 : Vector Maybe NNI := [coerce i for i in 1..10^6]
f4 x ==
v := v4
for j in 1..x repeat
for i in 1..10^6 repeat
empty? qelt(v, i)
x
g4 x ==
w := w4
for j in 1..x repeat
for i in 1..10^6 repeat
qretract qelt(w, i)
x
--
-- file: maybe.spad
)abbrev domain MAYBE Maybe
++ Description:
++ The type Maybe(R) represents either a value of type R, or absence/failure.
++ Using Maybe is a good way to deal with errors or exceptional cases without
++ resorting to drastic measures such as error. It replaces the usage of
++ Union(R, "failed").
Maybe(R : Type) : Exports == Implementation where
Exports == RetractableTo(R) with
construct : R -> %
coerce : List R -> %
empty : () -> %
++ empty() returns a value that indicates failure.
empty? : % -> Boolean
++ empty?(x) checks if x is empty().
retractable? : % -> Boolean
++ retractable?(x) checks if x is of type R.
qretract : % -> R
++ fast retract (no test for empty)
maybe : (%, R) -> R
++ maybe(x, default) returns x as type R if it's not empty(),
++ otherwise returns default.
maybe : (R -> R, %, R) -> R
++ maybe(f,x,default) returns f(unwrap x) or default if empty?(x)
if R has CoercibleTo OutputForm then CoercibleTo OutputForm
if R has BasicType then BasicType
if R has SetCategory then SetCategory
Implementation == add
Rep := List R
errMsg ==> "retract: the argument is empty()"
construct(x) == [x]
coerce(x) ==
if #x>1 then error "not singleton"
x
empty() == empty()$Rep
empty? x == empty?(x)$Rep
coerce(x:R):% == [x]
retractable? x == not empty?(x)
retractIfCan x == if empty?(x) then "failed" else first x
retract x == if empty?(x) then error errMsg else first x
qretract x == first x
maybe(x, default) == if empty?(x) then default else first x
maybe(f,x,default) == if empty?(x) then default else f(first x)
if R has CoercibleTo OutputForm then
coerce(x : %) : OutputForm == coerce(x)$Rep
if R has BasicType then
x = y == (x = y)$Rep
if R has SetCategory then
hashUpdate!(hs : HashState, x : %) == hashUpdate!(hs, x)$Rep
--
Bill Page
--
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 [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
