►
From YouTube: Rusty Days 2020 - Michalina Kotwica: Low-level optimization of algebraic and similar structures
Description
Agenda ► https://rusty-days.org/agenda
Slides ►https://rusty-days.org/assets/slides/02-low-level-optimization-of-algebraic-and-similar-structures.pdf
Playlist with all talks ► https://www.youtube.com/playlist?list=PLf3u8NhoEikhTC5radGrmmqdkOK-xMDoZ
Follow ►
Facebook: https://rusty-days.org/facebook
Twitch: https://rusty-days.org/twitch
Twitter: https://rusty-days.org/twitter
This video ►
While high-level advantages of functional programming and algebraic data structures in comparison to object-oriented programming are quite well known in the Rust community, numerous low-level advantages are not as commonly mentioned. While some programming languages use the functional approach as a means of optimization, Rust optimizes the very tools the functional paradigm is built upon.
In this talk, I want to present how Rust's approach to basic data structures (products/structs and coproducts/enums) is different from that of most functional programming languages. Further, I want to illustrate how low-level optimization is performed, which makes it possible, and what can be improved even further depending on how the language evolves.
A
A
A
A
A
So
the
the
problem
here
or
the
the
gorcha
here
is
that
the
the
way
it's
named
is
comes
from
the
sea
family,
while
the
algebraic
structures
is
more
of
a
functional
programming
way.
To
put
it.
So
that's
one
of
the
differences
and
one
of
the
reasons
why
it's
not
it's
not
that
obvious
what
what's
the
meaning
of
the
things
I'll
be
talking
about
so
first,
I
want
to
show
you
the
some
maps
of
typed
theory,
so
algebraic
structures
have
basically
two
key
operators.
A
So,
first,
if
you
have
a
point
from
the
previous
slide
defined
by
x,
y
and
color,
then
it's
multiplication,
because
if
you
take
the
number
of
values
of
that
x
field
can
take
and
why,
if
it
can
take
and
color
field
can
take,
then
if
you
multiply
them,
you
get
the
total
number
of
values
that
point
can
take
and
for
event.
From
the
previous
slide.
That
takes
one
of
three
types
of
event:
it's
it's
summation,
because
the
quit
variant
that
keep
respond
and
click
variant
are
separate.
A
So
it's
not
like
for
each
variant
of
quit.
You
have
one
variant
of
key
press
like
in
point,
but
what
is
important
here
and
that's
why
the
the
lower
part
of
of
this
slide
is
slightly
bigger
than
the
upper
one.
Is
that,
while
for
multiplication,
the
set
theory
and
type
theory
and
and
how
it's
coded
in
rust
is
basically
all
the
same
and
for
events,
it's
a
little
bit
different
because
for
sets
it's
not
just
summation,
it's
it's
a
special
type.
Addition
that
preserves
the
source
of
of
the
value.
A
A
A
However,
it's
also
pretty
useful
for
generics,
because
you
can
parameterize
generics
using
empty
tuple
to
show
that
there,
the
information
of
some
variant
of
an
anom
is
important,
but
it
carries
no
additional
information
and
one
of
the
examples
is
result
with
with
zero
empty
tuple
as
the
error
type.
As
you
can
see
here.
A
A
But
what
what
is
important
here
is
that
rust
has
has
the
way
of
dealing
with
empty
tuple,
quite
quite
different
from
other
languages
from
the
c
family,
because
the
the
size
of
the
empty
tuple
is
actually
zero.
So
be
aware
that
if
you
create
an
generic
type
which
doesn't
handle
well
types
that
carry
zero
bytes
of
information,
you
might
get
into
trouble.
So
remember
that
you
actually
can
create
a
vector
of
empty
tuples.
A
If
you
want
to
be
graphic
or
infallible
type,
if
you
want
to
stay
on
stable
rest,
it's
I
think,
most
known
for
results
which
which
do
not
carry
any
error
variant,
but
it's
also
used
for
expressing
that
the
function
never
returns
since
the
name
for
results.
It's
actually
a
little
bit
tricky
because
it
actually
deletes
the
the
whole
variant
that
it
occupies.
So
the
result
that
has
never
assets,
error
type,
actually
never
errors.
A
What
is
quite
interesting
here
is
that
the
never
type
that
is
lacking
in
language
in
other
languages,
like
simplest
or
java,
makes
it
possible
to
compose
not
only
compose
the
algebraic
data
structures,
but
also
discard
parts
of
them
without
suffering
runtime
codes,
because,
as
you
can
see
here,
we
do
have
the
our
result
of
computation
packed
in
the
results
structure
and
still
it
only
occupi
occupies
the
bytes
needed
to
actually
store
the
t
type
without
sacrificing
any
performance
on
memory
for
the
error
variant,
because
it's
never.
There.
A
A
So,
as
you
can
see
in
c,
the
the
order
of
the
fields
in
the
memory
layout
is
exactly
the
same
as
as
the
one
in
the
declaration
which
you
can
say
which
you
can
check
by
your,
not
use
your
wrap
c,
then
you
can
see
that
the
the
rust
structures
don't
really
care
about
the
order.
You
declare
your
fields
in
what
is
quite
important,
though
it
does
not
work
if
you
use
nested
structures.
A
So
it
has
to
occupy
the
same
bytes
and
therefore
we
can't
just
separate
its
fields
and
because
of
that,
rust
can
get
the
same
memory
layout
to
see
if
using
nested,
nested
fields
or
nested
structures.
But
otherwise
it
will
try
to
reorder
the
fields
in
the
most
compressed
way
possible.
And
there
is
even
a
special
fragment
to
ensure
this
for
coproducts
or
anoms.
We
have
even
more
optimizations.
A
We
do
have
numbers
like
your
size,
for
example,
that
treat
zero
as
invalid
value,
which
makes
it
work
pretty
much
like
with
pointers.
Considering.
That's
is
pretty
much
always
binary
zero
with
boolean
the
it's
a
little
bit
different,
because
false
and
rule
usually
map
for
zero
and
one,
but
because
of
that
two
or
three
are
still
are
still
there
to
be
used.
So
the
non-variant
is
equal
to
binary
two.
A
But
either
way
it's
the
size
is
reduced
by
the
by
that
optimization.
You
may
wonder
what
the
dots
here
mean
the
on
this
slide.
The
dots
are
there
because
in
the
c
representation
each
part
of
of
that
layout
states,
it
takes
a
full
32
bytes.
I
think
32
bits
I
think,
yeah
and
in
rust
it's
it's
a
little
more
a
bit
more
compressed.
A
So
you
do
have
the
part
for
the
data
and
part
for
the
so-called
discriminator,
which
discriminates
which
variant
of
the
anom
you're
at
and
in
theory.
If
you
have
a
an
animal
of
an
anum
so,
for
example,
a
result
of
an
option
or
an
option
over
option,
then
you
should
get
another
discriminator
for
the
outer
layer.
A
So,
for
instance,
if
you
have
an
option
of
an
option,
then
it
will
be
flattened
into
a
single
discriminator
that
treats
some
of
some
and
some
of
none
and
none
as
three
possible
variants
of
the
new
animal,
which
saves
quite
a
lot
of
space.
If
you
have
multiple
layers
of
that,
and
especially
many
layers,
if
you
have
only
if
you
consider
how
many
enums
of
the
kind
of
option
and
result
of
unit
and
async
etc,
you
can
stack
together.
A
But,
as
I
mentioned
it's
only
for
for
simple
atoms
and
what
I
mean
by
simple
is
atoms
that
have
at
most
one
field
that
that
holds
any
information
more
than
just
what
variant
it
is.
So
in
practice
it's
mean
it
looks
like
an
option,
so,
for
example,
it
could
be
and
a
result
with
the
error
type
of
unit
or
anything
similar
to
that.
A
A
To
show
you
why
that
optimization
is
a
real
deal,
a
real
feature
and
not
just
some
minor
stuff.
I
I
want
to
show
you
some
statistics
that
I
gathered
by
scanning
code
of
some
open
source
repositories,
so
I
took
some
some
standard,
truss
repositories,
so
last
c
compiler,
sir,
the
tokyo
regex,
my
own
master.
This
is
google,
google,
apis
and
logger
library
gathering
more
than
one
thousand
of
unknown
declarations,
and
here
is
what
I
found
most
of
annums
are
two
three
four,
maybe
five
variants
they
have.
A
So
I
checked
okay,
but
if
the
maximal
number
of
fields
is
one,
then
what
is
the
minimal
number
of
fields
or
what
is
the
number
of
fields
that
are
non-zero,
and
it
turned
out
that
in
most
cases,
if
you,
if
we
have
an
anom
with
one
field
at
most,
then
in
most
cases
both
variants
do
carry
a
value
so
that
images
optimization
doesn't
apply.
But
it's
over
15
percent,
when
it
does
so.
A
That
is
also
let's
say:
it's
also
connected
to
algebraic
structures
are
futures,
and
you
know
it's
it's
not
that
that
that
obvious
to
see
because
and
structures
are
the
dictionary
definitions
of
product
and
co-product
from
type
algebra
while
futures
are
that
abstract
thing
that
is
defined
by
what
it
does
it's
a
trait
right,
but
considering
how
it's
implemented
in
rust,
both
futures
and
iterators
are
actually
implemented
as
animals.
So
if,
if
you
ever
implemented
a
future
on
your
own,
then
you
probably
do
know
it.
A
What
could
be
done
is,
of
course,
implementing
the
block
structure
as
a
structure
is
instead
of
an
atom,
and
in
this
particular
case
it
would
be
a
good
idea,
probably
because
we
use
signals
all
the
time
and
the
only
things
that
would
reuse
the
memory
are
the
id
and
data
and
and
error
is
probably
not
that
big,
but
in
other
cases
well
it
bloats
up
to
potentially
enormous
sizes.
So
the
problem
here
is:
it's
not
really
obvious.
A
A
Check
which
fields
are
available
at
which
stage
of
the
future
execution
make
it
a
table
or
any
graphic
representation.
You
want
and
check
which
fields
are
used
at
the
same
time,
and
if
they
are
not
never
used
at
the
same
time,
then
they
can
reoccupy
the
same
space
just
like
here
in
this
example,
if
we
have
some
bounds
or
indexes
in
a
vector
and
an
iterator
based
on
them
and
the
iterator
isn't
available
on
the
same
stage
of
the
future
execution
as
the
indexes.
A
A
A
Yes,
it
does
happen
as
long
as
one
of
the
variants
of
the
result
is
a
unit
type
or
another
type.
Well,
if
it's
another
time
that
it's
not
an
optimization,
actually,
of
course,
if
it's
a
unit
type,
then
the
result
is
practically
working
like
an
option,
so
it
works
for
any
anoms
that
that
look
like
an
option.
You
could
say
so
they
have
at
most
two
variants
and
at
most
one
of
them
carries
some
information.
A
Well
there
I
I
heard
that
there
are
plans
to
enable
more
than
two
variants,
but
then
you
would
need
to
have
more
fields
that
have
that
particular
that's.
This
particular
characteristics
like.
If
you
have
a
single
variant
of
two
pointers,
then
of
course
you
could
you
could
encode
other
variants
by
null
on
either
of
these
pointers,
but
then
the
problem
with
that
is
that
you
would
need
to
do
multiple
checks
which
isn't
really
good
for
performance.
So
that's
why
it's
freaking
not
really
that
trivial
jaimo
kond
on
twitch
asks.
A
A
A
Yes,
the
anum
is
an
implementation
of
a
state
machine,
as
you
could
see
on
the
slide
of
mine.
With
that
an
over
presentation,
I
I
showed
you,
the
state
changes
or
the
possible
stage
changes
by
arrows.
It's
a
little
more
explicit
in
the
next
slide
when
you
have
a
table
with
availability
of
the
fields.
A
A
A
A
A
Optimal
in
the
performance
sense,
it
would
be
in
the
memory
layout
as
of
course,
in
fact,
if
it's,
if
it's
ff
case
or
minus
one,
is
also
a
popular
idea,
then
nothing
stops
us
from
that.
I,
I
think-
and
I've
actually
seen
some
implementations
of
that,
and
I've
done
an
implementation
implementation
of
that
myself.
A
As
for
us
for
checking
if
something
is
less
than
something
or
greater
than
something,
not
so
in
easy
on
the
language
level.
So
the
problem
here
isn't
the
technical
aspect,
but
it's
the
safety
aspect,
in
this
case
the
safety
aspect
and
the
and
the
proof
that
it's
indeed
more
performant.
So
you
could
say
that
it's
it's
zero,
because
we
don't
want
to
wonder
if
it's
the
best
choice,
both
performance,
wise
and
size,
wise.
A
Well,
it
depends
on
what
you
mean
by
handling,
because
from
the
code
perspective,
it's
still
just
an
option
of
optional
option
etc
of
unit.
But
yes,
it
will
compile
down
to
a
single
bite.
So,
yes,
it
is
possible.
It's
just
a
corner
case
that
I
wouldn't
expect
to
see
in
a
while.
But
yes
it
it
is
possible
and
it
is
possible
just
in
the
current
versions,
or
so
I
think
at
least
maybe
255
repetitions
unless
it
would
crack
the
compiler
considering
the
level
of
nesting.
But
that's
another
thing
really.