►
From YouTube: Writing Performant Concurrent Data Structures by Adrian Alic - Rust Zürisee March 2023
Description
Writing performant concurrent data structures in Rust can be challenging, and often requires subversion of Rust's ownership guarantees. In this talk I'll be using a multi-producer single-consumer queue as a case study for writing performant code, crafting safe abstractions, sniffing out undefined behaviour & concurrency issues, and avoiding pitfalls during benchmarking.
Slides: https://github.com/rust-zurichsee/meetups/tree/master/2023-03-28_embedded-hpc
Adrian's Blog: https://alic.dev/
Watch more of our meetup: https://www.youtube.com/playlist?list=PL85XCvVPmGQipj690WrVgsnU4K4x7qFGy
Join us next time: https://www.meetup.com/de-DE/rust-zurich/
Would you like to chat or give a talk? Join us in our Matrix room:
https://matrix.to/#/#rust-zuerisee:matrix.coredump.ch
Chapters:
00:00 Intro
01:39 Motivation
04:53 The Ideas for more speed
10:47 The Memory Model
18:48 Implementation in Rust
33:43 Crafting Safe Abstractions
45:41 Runtime Analysis with Miri
48:32 Conclusion
53:16 Questions
A
Foreign,
hello,
everybody
thanks
for
coming
it's
nice
to
see
so
many
people
here,
just
a
short
introduction.
My
name
is
Adrian
alich
I'm,
a
software
engineer
at
Divinity,
so
my
main
time
is
actually
spend
writing
rust,
which
I'm
really
thankful
for,
and
today
I'll
be
talking
about.
Concurrent
data
structures
and
I
recently
wrote
a
crate
which
is
incredibly
cursed,
but
I'll
use
it
as
a
case
study
reference
throughout
this
presentation
right.
A
So
it's
an
mpscq
and
for
anyone
who
doesn't
know,
mtsc
stands
for
multi-producer
single
consumer
queue
and
basically
what
it
means
is
that
we
have
multiple
concurrent
reducers
push
some
kind
of
data
into
a
shared
queue.
So
there's
some
kind
of
data
stream
and
it
happens
concurrently
or
in
parallel
and
the
consumer
is
a
single
entity
and
it
needs
to
process
these
events
in
some
kind
of
like
a
Serial
form,
and
the
problem
with
this
is
how
we
deal
with
the
concurrency
of
The
Producers.
A
So
how
do
we
achieve
this
form
of
communication
and
yeah
we'll
go
over
like
several
details,
so,
first
of
all,
we'll
think
a
bit
about
how
to
write
such
a
queue
in
Rust.
How
to
make
it
fast,
so
I'll
talk
a
bit
about
a
few
optimizations
you
can
use
and
then
also
how
to
reason
about
correctness,
because
anything
relating
to
unsafe
data
structures
is
a
bit
of
a
minefield,
and
I
would
like
to
motivate
this
with
an
example
and
the
previous
talk
is
actually
quite
relevant.
A
So
basically
at
the
bare
metal
system,
a
small
SOC,
a
risk
5
based
multi-core
system
and
I
needed
to
write
a
printf
command.
But
the
problem
is
I,
don't
have
a
Linux
operating
system,
it
was
pure
bare
metal
and
right.
I,
don't
have
anything
except
just
my
your
instructions
and
pure
memory
access.
So
this
is
like
an
example
of
how
it
would
look
like
on
right
side.
A
This
is
like
a
sci-fi
SOC,
5
cores,
and
this
printf
command
was
supposed
to
be
used
by
my
bootloader
and
my
bare
metal
task,
scheduler
to
just
print
messages
to
a
Serial
Port.
So
I
can
have
just
some
kind
of
information
on
what
my
course
are
doing,
but
the
problem
is
that
the
uart
is
a
Serial
device
and
all
of
these
five
cores
are
working
in
parallel.
So
this
presents
a
like:
it
presents
basically
a
race
over
the
uart,
so
there
needs
to
be
some
form
of
synchronization
and
there
are
many
ways
to
achieve
it.
A
The
most
common
way,
the
most
simple
way,
I
guess,
if
you
have
an
operating
system
or
threading
or
some
kind
of
task
system,
is
to
use
a
form
of
mutex
or
you
can
have
all
of
the
five
course
spin
on
a
atomic
variable
like
semaphore
or
and
then
just
organize
the
access
to
the
uart.
This
way
right,
but
there
is
a
problem
with
this
and
I
visualized
it
here.
A
So
it
increases
a
bit
of
latency
and
the
same
thing
also
happens
for
the
third
process,
in
which
case,
because
of
the
way
we
we
resolve
or
we
like
giveaway
again,
access
to
the
uart
can
depend
on
some
kind
of
priority.
Sometimes
we
can
have
an
important
situation
where
one
task
will
allow
basically
have
a
an
unpredictable
about
amount
of
latency
added
which
basically
blocks
itself
until
it
can
access
the
print
command
again.
A
So
this
is-
and
the
interesting
thing
is
like
this-
doesn't
only
apply
to
spin
locks
right
if
we
have,
for
instance,
the
second
process
after
it
sees
that
it
can
print
anymore,
it
can
print
itself
and
then
just
the
the
operating
system
can
patch
in
another
task.
The
problem
is
why
we
maintain
utilization
and
throughput.
We
do
increase
latency
in
any
case.
So
if
you
have,
if
it's
in
your
best
interest
to
reduce
latency,
then
this
type
of
locking
will
cause
unpredictable,
Jitter
and
yeah.
A
But
once
you
start
measuring,
you
are
altering
like
how
the
system
behaves
and
introducing
noise.
So
you
might
increase
the
like
variance
in
your
measurements
and
increase
the
noise
floor,
and
suddenly
your
signal
goes
away
so
having
some
kind
of
low
overhead
debugging
can
absolutely
help
in
many
cases,
which
is
why
these
weight-free
cues
are
very
practical
right.
So
this
would
be
just
an
example
of
how
you
would
maybe
design
an
mpscq.
A
There
are
many
ways,
and
there
are
many
trade-offs,
so
one
trade-off
you
can
make
is
to
say
that
you
have
a
fixed
size
like
your
queue
is
not
unbounded,
it's
actually
bounded,
and
maybe
you
can
also
say
that
it
has
felon
overflow
Behavior,
meaning
that
once
the
queue
is
full,
you
can't
write
to
it
anymore
right.
This
would
be
like
one
characterization,
which
I
chose
in
my
case,
so
we
have.
The
design
is
basically
for
every
single
producer.
A
We
have
a
single
fifo
ring
buffer
allocated,
which
is
solely
owned
by
the
producer,
and
the
producer
pushes
data
to
this
threat.
Local
FIFA
ring
buffer
and
the
consumer
pulls
it,
and
the
nice
thing
about
this
is
that
the
synchronization,
like
the
synchronization
mechanisms
and
the
the
like
the
workings
of
how
memory
is
shared,
is
very
well
understood
for
these
ring
buffers,
so
they
can
be
written
in
a
relatively
Safe
Way
right.
So
an
example
of
how
you'd
write
a
ring,
buff
and
rest
would
be,
and
I
call
this
like
tlq.
A
A
A
This
is
this
is
a
queue
that
has
an
array
of
threat,
local
cues
and
we
store
the
buffered
and
the
head
and
the
tail
and
then
the
buffer
again-
and
this
has
a
bit
of
a
cache
locality
problem
for
certain
kinds
of
traversals.
For
instance,
the
consumer
needs
to
actually
Traverse
both
head
and
the
tail
of
every
single
producer
in
order
to
find
out
if
a
q
is
empty
or
full
or
has
elements
in
it.
A
So
what
you
want
to
do
is
is
like
basically,
the
problem,
especially
with
this
is
that
if
the
buffer
is
large,
which
is
generally
is,
then
you
introduce
a
cache
Miss.
Not
only
that,
because
we're
doing
a
concurrent
data
structure,
a
cache
Miss-
will
also
mean
maybe
an
atomic
transaction
like
an
atomic
load
which
increases
additional
cash
coherence
in
traffic
and
that
has
even
more
severe
impact
than
a
pure
cash
Miss
in
some
cases.
A
So
this
is
something
that
is
really
rough,
and
this
is
also
something
you
will
find
often
in
game
development,
PCS,
Style,
game
development,
where
you
have
a
big
struct
lots
of
fields
in
it,
and
you
want
to
you,
have
an
array
of
all
these
structs
and
you
want
to
integrate
through
a
particular
field
of
all
of
these
objects
and
to
fix
this.
There
is
something
called
struct
of
arrays,
and
what
we
do
here
is
very
relatively
simple.
A
So
this
is
generally
applicable
and
Zig
actually
has
a
built-in
support
for
for
for
changing
array
of
structs,
the
structs
are
very
like
changing
between
them.
Russ
does
not
have
that
yet,
but
maybe
it
will
be
at
some
point
in
the
future
right
and
with
this
we
can
now
take
a
step
back
and
think
a
bit
about
memory.
A
The
reason
is
that
okay,
so
now
we
have
the
just
the
basic
data
structure,
but
there
are
some
problems,
and
that
is
that
a
lot
of
times
when
you're
writing
a
concurrent
data
structure,
especially
if
it
needs
to
be
very
performant,
writing
unsafe
courses.
The
code
is
quite
nice,
but
especially
when
dealing
with
concurrency
the
failure
modes
are
sometimes
very,
very
difficult
to
understand,
they're
difficult
to
debug,
and
sometimes
they
happen
very,
very
rarely
and
only
on
certain
architectures.
A
I
can
give
you
an
example.
The
first
prototype
of
my
queue
was
written
on
the
basis
of,
but
at
least
my
fourthly,
understanding
of
memory
models,
which
was
based
on
how
x86
processors
behave
so
I,
just
I
studied,
like
I,
just
sprinkled
ordering
relaxed
all
over
my
queue
everywhere,
like
pepper
and
of
course,
it
blew
up
once
I
ported
it
to
my
MacBook,
because
it
has
a
different
memory
model
and
yeah.
A
Basically,
I
didn't
realize
that
what
I
actually
want
to
write
is
portable
software
and
incorrect
software
and
I
didn't
realize
that
the
semantics
I
chose
to
develop
against
were
like
incorrect.
I
was
I,
was
developing
against
the
x86
semantics
and
which
you
can't
reorder
stores
in
a
store
buffer
or
loads
in
a
load
buffer
right,
and
it
doesn't
stop
there.
Of
course,
this
is
like
a
table
where
you
can
see
on
the
top.
A
You
have
all
kinds
of
different
processor
architectures
and
the
x86
is
actually
one
of
the
most
one
of
the
most
conservative
out
of
all
of
the
these
out
of
order,
processors
yeah.
It
basically
doesn't
reorder
its
instructions
that
aggressively
all
of
these
other
risk
chips
and
mips
power
arm
they're.
Much
more
aggressive
and
the
alpha,
which
is
very
fitting
name
because
it's
completely
insane
it
also
reorders
dependent
loads
yeah,
which
is
an
absolute
Maniac.
A
So
a
good
name
choice
for
this
instruction
architecture
right
so
basically
Hardware,
is
very
varied
and
most
of
the
time
people
won't
actually
want
to
write
portable
software
and
not
only
a
software
that
is
geared
towards
specific
semantics.
So
we
I
needed
to
change
my
thinking,
I
needed
to
develop
against
the
language
semantics.
A
And
this
is
where
the
C11
memory
model
comes
in,
so
Russ
does
not
have
a
formerly
very
formally
specified
memory
model,
but
currently
just
copies.
What
CPUs
plus
does
and
because
it's
relying
on
llvm
it
just
emits
the
same
instructions
and
intrinsics
that
that
clang
would
use
and
right
this
other
memory.
Ordering
spec
of
of
C11
is
actually
pretty
great
because
it
includes
a
very
nice
overview
of
cache
coherency
and
also
explains
to
you
what
it
means
for
things
to
be
ordered
before
other
things.
A
So
highly
recommended,
and
with
this
in
mind,
we
can
actually
think
a
bit
about
how
our
queue
behaves.
So
since
basically
I
said
in
the
first
part
that
our
mpscq
is
just
an
is
just
a
collection
of
different
fifo
buffers
one
for
each
producer.
So
we
can
actually
look
at
an
isolated
case
where
we
have
the
single
producer.
Only
and
the
single
producer
single
consumer
case,
the
semantics
are
quite
simple.
So
what
happens
when
you
want
to
push
data
to
the
queue?
A
So
you
have
the
tail
and
the
head
and
the
producer
the
producer
pushes
data
to
the
queue
by
first
writing
to
the
buffer
and
then
incrementing
the
head.
Actually,
it
needs
to
read
the
tail.
Read
the
head
calculate
the
capacity.
Then
it
writes
data
to
the
queue
and
then
increments
the
head,
so
the
head
index
is
not
allowed
to
be
modified
before
the
producers
finish
writing
data.
So
this
is
your
first
ordering
that
you
need
to
enforce
in
your
code
and
similarly
the
consumer,
the
consumer
generally,
but
it
does
it.
A
It
reads
the
tail
and
the
head
sees.
If
there
are
any
elements
present,
then
it
reads:
data
from
the
queue
and
after
it's
done
needs
to
increment
the
tail.
So,
basically,
when
you
explain
yourself
or
explain
to
yourself
the
how
the
queue
is
or
how
any
data
structure
is
supposed
to
work,
whenever
you
use
this
has
to
happens
before
this,
then
you
know
where
you
need
to
put
your
release
acquired
pairs.
A
So
the
consumer
basically
needs
to
read
the
data
and
finish
reading
it
and
then
only
increment
the
tail,
and
the
nice
thing
here
is
that
we
actually
have
no
competing
store
operations
on
either
tail
or
heads.
So
that
means
we
don't
need
any
type
of
atomic
read
copy,
update,
read,
modify
right,
Primitives
like
Cas
or
llse.
A
A
So
here
in
the
first,
in
the
first
case
on
the
left,
we
have
a
push
function
and
in
the
push
function
we
write.
Data
like
this
is
basically
the
third
line
says:
write
data
to
the
queue
and
then
update
the
index.
So
this
is
the
first
ordering
we
want
to
have
and
when
we
say
ordering
we
say
we
want
an
external
like
another
process
that
runs
on
another
processor
to
observe
them
in
that
order,
and
the
same
thing
goes
for
the
pop.
A
We
want
to
read
an
index,
then
read
data,
and
this
is
a
bit-
that's
actually
a
bit
annoying.
So
the
thing
is,
how
can
you
read
the
data
if
you,
if
you
did
not
read
the
index
before,
because
the
index
is
determines
the
address
from
which
you
perform
the
read?
So
how
can
this
ever
be
reordered?
And
the
answer
is
that
this
is
a
wrong
question
to
ask
because
you're
not
developing
against
the
processor
or
architecture,
semantics
you're,
developing
against
language
semantics
and
the
C11
memory.
Spec
has
no
notion
of
address
dependency
or
control
dependency.
A
These
things
happen
on
the
computer
architecture
level.
So,
if
you,
if
you
make
certain
assumptions
about
how
these
things
like
are
supposed
to
be
ordered
based
on
some
kind
of
dependency,
then
you're
already
committing
the
first
cardinal
sin
and
yeah.
This
is
something
that
happened
to
me.
Just
because
you
can't
observe
it
on
most
architectures
does
not
mean
that
your
code
is
technically
not
undefined
behavior.
A
And
this
is
how
it
would
look
like.
Basically
here
we
have
released
in
the
choir
and
the
same
thing.
You
will
have
a
second
time
in
this
code
and
with
that,
we
can
now
assume
that
the
code
is
mostly
correct
for
this
push
and
pop
operation.
Now
we
can
think
a
bit
about
how
to
make
it
bit
more
performant,
because
as
long
as
the
concurrency
works,
the
rest
can
be
relatively
well
handled
and
I
like
to
start
with
the
first
bread
and
butter.
A
Optimization
that
you
want
to
have,
which
is
the
avoidance
of
false
sharing.
So
I
said
previously
that
we
employ
this
optimization
of
a
construct
of
arrays,
where
we
have
all
of
the
offsets
of
our
queue
stored
in
the
first
part
of
our
allocation,
which
means
they're
all
packed
together,
and
this
is
an
example.
Obviously
you
wouldn't
choose
such
big
offsets,
but
let's
say
we
have
64-bit
tails
and
heads
eight
producers
and
all
of
them
packed
together,
so
they
would
occupy
two
64
byte
cache
lines,
and
so
in
the
second
cache
line.
A
What
happens,
then,
is
that
every
single
processor
will
consist
constantly
claim
exclusive
access
to
this
cache
line,
and
then
the
cash
coherence
protocol
will
cause
lots
of
invalidations
and
cash.
Coherency.
Traffic
will
completely
saturate
the
interconnect
which
causes
terrible
latency.
So
this
is
actually,
if
you
have
massive
cache
like
false
sharing
and
massively
invalidate
all
of
these
cache
lines.
What
you're
essentially
doing
is
you're
locking
on
a
hardware
level.
A
So
here
you
have
some
kind
of
Dead
Space,
there's
no
data
in
there
and
every
single
tail
and
head
occupied
their
own
cache
line.
So
there
is
no
false
sharing
here
now.
There
is
actually
a
interesting
other
way.
You
can
think
about
this,
so
this
fully
padded
version
has
actually
one
downside,
namely
we.
We
have
a
multi-producer
single
consumer
case,
so
we
have
one
consumer
and
it
pops
all
of
the
data
of
all
of
the
producers
of
their
cues
at
once.
A
So
we
don't
actually
have
false
sharing
on
the
consumer
side
in
this
case.
That
means
that
it
might
make
sense,
in
certain
cases
to
pack
tightly
all
of
the
Tails
together.
So
this
is
like
a
bit
of
a
hybrid
layout,
and
in
this
case
what
we
can
do
is
we
can
have
the
consumer
first
read
all
of
the
tails
and
then
after
it's
done
pulling
all
the
cues
and
Performing
all
the
reads
that
it
needs
once
it
needs
to
update
details.
A
A
So
this
is
just
like
one
right,
which
is
very
nice,
and
you
will
see
this
optimization
and
lots
of
log
free
weight,
free
algorithms,
where
you're
using
you're
trying
to
be
very
frugal
with
the
size
of
your
pointers
in
some
cases,
because
then
you
can
perform
batch
updates,
and
this
would
be
an
example
of
how
you
would
implement
the
former
case
in
Rust.
Yeah.
Sorry,.
A
Yes,
yeah,
but
there's
one
difference
and
tell
us
that,
like
basically
reading
a
shared
cache
line
does
not
invalidate
it.
So
basically,
I
was
thinking.
If
you
have
one
consumer
and
32
producers,
all
of
them
updating
detail
all
of
them,
updating
the
queue
they're
not
going
to
cause
invalidations.
That's
why
right
I
also
thought
about
it.
I
also
measured
both
of
them
so
just
be
sure
yeah
right.
But
it's
a
very
good
point.
That's
actually
another
thing.
A
A
So
what
I
did
was
I
had
a
16
byte
a
bit
integer
I
knew
type
it
with
a
tail
or
head
abstract
and
then
just
align
it
with
this,
like
proc
macro
and
this
attribute,
and
then
once
you
include
it
in
an
array,
it
will
automatically
happen
like
that.
So
the
thing
that
also
might
be
interesting,
so
the
64
is
hard-coded
and
it's
not
an
it's,
not
a
variable
that
you
can
set.
A
It's
not
a
constant,
because
this
stuff
is
replaced
on
the
ASD
level,
so
yeah,
it's
also
an
intrinsic
for
the
rest
compiler.
What
you
could
do,
however,
you
could
use
either
the
config
attribute
macro
or
you
use
the
cross.
B
mutil,
crate
crossbeam
is
a
crate
which
has
lots
of
these
high
performance,
concurrent
data
structure,
implementations
that
are
not
as
cursed
as
mine
and
like
well
written
and
they
have
all
kinds
of
these
utilities.
A
So
cache
padded
is
just
a
wrapper
and
it
makes
sure
that
your
whatever
you
wrapped
is
properly
aligned
depending
on
your
architecture.
So
if
you
are
an
Intel,
it
will
sorry.
If
you
are
an
x86,
it
will
actually
align
everything
to
128
byte
cache
line
because
they
said
in
the
documentation
that
they
are
worried
about
the
hardware
prefetcher
pulling
data
in
I'm,
not
sure
I
didn't
observe
any
difference.
So
that's
why
I
usually
chose
to
just
choose.
A
64
byte
and
I
recently
wrote
also
a
blog
post
in
which
I
documented
some
of
these
problems
with
file
sharing,
and
this
was
basically
a
benchmark
on
the
left
side.
You
can
see
the
the
left
graph
shows
the
maximum
contention,
so
you
have
all
nine
producers
constantly
pushing
data
to
a
queue
and
you
can
see
the
performance
penalties
like
6X
to
10x,
sometimes-
and
that's
that's
the
latency
that
we're
actually
trying
to
avoid
so
by
reducing
like
fall,
sharing,
we're
actually
getting
lots
of
latency
improvements.
A
And,
of
course,
if
you
don't
have
much
contention,
then
you're
not
going
to
have
much
of
a
penalty
of
false
sharing.
But
then
again,
why
are
we
doing
weight
free,
producing
producer
and
consumer
use?
We're
trying
to
optimize
for
the
high
contention
case,
because
we
would
try
to
have
a
like
a
limit
to
how
much
latency
we
incur.
Otherwise
we
could
just
use
locking-
and
this
is
generally
a
thing-
if
you
don't
have
much
contention,
locking
can
sometimes
be
much
faster.
A
Sorry
yeah,
the
x-axis
is
the
number
of
producers
and
there
are
two
bars.
One
is
gray.
One
is
white,
the
gray
one
is
the
packed
layout
which,
where
all
of
them
are
like
in
one
cache
line
and
the
hybrid
layout
is
the
thing
I
showed
where
you
have
only
the
Tails
packed,
but
the
head
aligned
to
a
button
and
I'm
here
right,
I
yeah.
If
you
follow
the
link,
then
you
will
see
all
kinds
of
pictures
for
different
for
different
architectures
and
different
numbers
of
producers.
A
But
I
did
manage
to
add
the
access
in
matplotlib
didn't
know
how
to
do
it
right
right.
So
I
spoke
earlier
about
this.
This
ability
to
do
an
atomic
batch
update.
So,
let's
say
all
of
your
tails
are
tightly
packed
into
a
single
small
area.
Then
you
can
do
a
very
efficient
update,
but
this
means
you
need
to
be.
You
need
to
have
very
small
footprint
for
your
indices.
You
can't
just
have
to
be
64-bit
pointers,
so
one
very
commonly
used
optimization
here
is
to
use
point
and
compression.
A
You
often
use
pointer
compression
together
with
this
batch
update
and
the
pointer
compression
just
means
that
we're
reducing
the
addressing
granularity
of
our
queue.
So
if
we
have
a
normal
index
like
0,
1,
2
3,
4
5,
we
just
shift
it
by
one
to
the
right,
and
now
we
have
like
basically
a
more
actually
what
we
do
is
we
mask
the
last
bit
so
now
the
zero
and
the
one
and
the
two
refer
to
either
the
first
element
or
the
second
and
the
first
like
number.
A
One
refers
to
two
or
three
number
two
refers
to
405.
So
what
we
do
is
with
a
smaller
with
a
smaller
like
amount
of
numbers,
we
can
address
a
larger
amount
of
memory
and
the
problem
is
that
we
lose
accuracy,
so
the
simplest
one
would
be
a
Boolean
which
would
be
just
one
massive
index.
That
basically
says
if
your
Q
is
empty
or
full-
that's
not
very
helpful.
So
you
need
to
choose
something
in
between
and
reducing
this
addressing
granularity
has
one
downside,
but
many
many
upsides.
A
So
this
is
how
it
would
look
like
in
the
first
example,
you
have
like
the
accurate
tail
of
the
queue
which
is
right,
stored
there
and
on
the
left
side,
you
have
three
empty
element
like
three
places
where
you
can
put
elements
inside
and
the
second
case.
This
is
what
the
producer,
for
instance,
would
see.
So
this
would
be
a
compressed
index
and
because
we
need
to
be
pessimistic
when
it
comes
to
the
addressing.
A
The
only
thing
that
the
producer
sees
is
that
this
the
tail
is
at
position
one,
and
that
means
that,
for
the
producer
it
looks
like
there's
only
space
left
for
two
elements
and
yeah.
So
basically
we're
wasting
one
element
worth
of
space
if
we
compress
the
index
by
one-
and
that
only
happens
if
RQ
is
very
full.
A
In
this
case
we
lose
four
bits
worth
of
addressing
which
only
happens
like
in
this
full
case.
So
this
is
really
not
a
problem,
and
this
is
how
it
would
look
like.
So
you
have
the
consumer
and
it
has
a
shared
tail
and
a
local
tail.
The
local
tail
is
the
accurate
tail.
It's
the
one
here
on
the
top
and
the
share
tail
is
the
compressed
index.
A
So
it's
the
thing
that
the
producer
sees
it's
the
thing
that
makes
the
producer
aware
of
how
much
data
is
still
allowed
to
be
inserted
into
the
queue
and
yeah.
So
when
you
update
the
tail,
you
just
write
to
the
accurate
tail,
the
actual
value,
and
when
you
want
to
submit
it,
you
just
do
an
ordering
release
and
update
a
compressed
version
of
this
tail.
A
Another
optimization
that
you
can
do
to
use
caching
of
offsets.
So
if
you
actually
perform
very
clever
types
of
caching,
you
can
avoid
avoid
in
many
cases,
get
a
cash
currency
traffic.
Sometimes
then,
the
false
sharing
avoidance
actually
has
downsides.
It
doesn't
happen
often,
but
you
need
to
measure
or
in
the
effects
of
performances
of
performance
improvements
that
all
together
not
individually,
so
local
caching
is
a
pretty
simple
to
imagine
so
you
have
let's
say
we
have
a
queue,
and
this
is
from
the
perspective
of
the
producer,
that's
important.
A
So,
on
the
left
side,
you
have
a
tail
on
the
right
side.
You
have
a
head,
the
middle
some
elements
and
the
producer
just
pushed
these
elements
to
the
queue
now
the
next
moment.
Basically
the
that's
all
the
the
producer
remembers.
So
it
does
not
know
where
the
tail
currently
is
like.
After
having
pushed
to
to
the
queue.
Anything
could
have
happened
so
right
now
it
doesn't
know
exactly
where
the
tail
is.
A
The
consumer
has
not
popped
any
data
off
and
just
add
data
to
the
queue
until
we
reach
the
old
position
of
the
tail,
at
which
point
we
then
perform
the
read
operation
and
possibly
reveal
more
data
that
is
free
to
be
pushed
so
yeah
in
this
case,
and
also
if
the
queue
is
very
very
long.
You're
gonna
reduce
your
Atomic
reads
on
the
tail
by
orders
of
magnitude.
So
this
is
a
great
optimization
and
this
is
gonna
your
lots
of
benefits.
If
your
cue
is
especially
large,
yeah.
A
Yeah
I
should
also
say
that
okay,
the
way
I
designed
my
queue,
it
was
supposed
to
be
a
like
a
Serial,
Port,
debugger
kind
of
and
also
a
tracing
tool,
and
what
I
did
was
I
submitted,
variable
size,
bite
slices,
so
I
didn't
submit
like
like
a
certain
number
of
number
of
elements
that
were
the
certain
size.
So
the
push
and
pop
operations
are
actually
big,
mem,
copies
right.
A
So
the
nice
thing
in
rest
is
that
we
have
quite
a
few
tools
to
to
to
create
safe
abstractions,
because
in
many
of
those
cases
you
will
have
to
deal
with
raw
pointers
in
raw
allocations,
and
it
can
get
quite
ugly.
So
it's
very
nice
if
you
can
ensure
that
the
user
facing
side
of
your
API
is
fully
fully
safe.
This
is
the
idea
of
rest,
and
there
are
some
problems.
So
the
first
one
is
that
the
borrow
Checker
and
the
lifetimes
in
general.
A
They
can't
reason
about
any
kind
of
arbitrary
concurrent
data
structure.
They
you
have
to
help
it.
So
that's
actually
the
reason
why
you
will
see
lots
of
interior
mutability
things
and
unsafe
cell,
and
the
reason
for
for
these
constructs
is,
is
that
the
Border
Checker
has
limits
and
yeah.
Basically
Atomic
atomics
are
the
best
example.
You
can
share
a
you,
can
share
a
shared
reference:
that's
not
mutable
to
all
kinds
of
threads
completely
safely
and
then
perform
actually
mutation.
A
That's
that's
an
example
of
interior
mutability
and
a
lot
of
times
when
you're
writing
your
handmade
concurrent
data
structures.
You
will
have
to
maybe
think
about
these
things:
how
to
present
mutability
shared
mutability
to
your
users
without
breaking
the
safety
guarantees
and
especially
aliasing
guarantees
right.
A
So
you
can
actually
encode
the
permissions
in
there
and
then
also
the
benefit
of
new
typing
is
that
you
can
put
in
constant
generics,
which
maybe
the
constant
generics
might
characterize
your
data
structure
and
then,
and
with
this
you
can
basically
keep
track
of
your
of
the
semantics
of
your
queue
and
how
to
perform
masking.
And
you
can
place
assertions
everywhere,
and
this
basically
hinders
you
from
accidentally
mixing
up
certain
pointers
all
on
your
code
base.
A
So
this
would
be
an
example
of
how
a
consumer
or
producer
my
keyword
look
like
if
you
use
these
nice
new
types
and
you
you
can
immediately
think
about
the
semantics
of
the
queue
which
is
the
consumer
is
only
allowed
to
read
from
the
buffer,
not
to
write
to
it
and
also
only
allow
to
read
ahead.
It's
allowed
to
modify
all
the
Tails,
so
we
have
bridge
by
tail,
read
only
head
read
only
buffer
and
for
the
producer
everything
is
exactly
flipped,
so
we
have
rewrite
head,
read,
write
buffer,
but
read
only
tail
so
already.
A
A
There
is
one
problem,
and
that
is
that
is
very
unergonomic
to
write
and
it
looks
extremely
ugly.
So
one
way
you
can
fix
this
is
by
maybe
using
proc
macros,
but
ideally
you
would
use
something
like
constant
generic
Expressions,
which
is,
you
could
say,
rust's
limited
support
of
dependent
types,
but
it's
an
unstable
feature.
It's
not
supported
very
well,
it's
actually
supposed
to
be
deprecated
soon
for
something
else
so
yeah.
This
is
unfortunately,
but
if
you're
interested
in
Idris,
which
is
a
dependently
type
programming,
language
I
highly
recommend
it.
A
If
you
are
into
this
generic
style
of
programming,
and
so
the
next
one
would
be
something
known
as
raii
I'm,
not
sure,
if
there's
a
acronym
in
in
rest
for
this,
but
we
can
think
a
bit
about
our
pop
operation
for
the
consumer.
So
what
the
consumer
does
it?
It
reads
into
the
queue
which
is
just
a
byte
buffer
and
well.
It
needs
to
read
from
it
and
then
one
thing
we
could
do
is
we
could
copy
data
from
it,
because
this
memory
is
volatile.
A
It's
ring
buffer,
it
gets
overwritten,
so
we
have
limited
time
to
do
something
with
it.
One
way
would
be
to
like
read
from
it
by
copying
it
and
returning
a
vector
so,
and
one
problem
here
is
that
you
have
a
heap
allocation,
which
is
maybe
not
ideal,
as
in
some
case
you
don't
even
have
the
Heap
so
and
also
you
don't
really
can
you
can
really
specify
the
amount
of
bytes
you
expect,
for
instance,
if
you
want
only
five
bytes,
then
you
need
to
make
your
type
signature
more
complex.
A
Maybe
this
is
not
the
best
idea.
Another
thing
that's
very
C,
like
I,
don't
know,
I
didn't
write
much
C,
but
I
think
that's
how
it
works
like
you
pass
a
mutable
reference
to
to
some
kind
of
byte
buffer
to
the
queue
and
then
the
queue
populates
it
I
mean
actually
the
consumer
then
populates
it
and
returns
to
you,
the
number
of
bytes
written
to
it.
This
is
quite
nice
because
here
you
can
specify
how
many
bytes
you're
allowed
to
like
expecting
to
accept.
A
A
Another
thing,
probably
the
best
thing
that
you
would
like
to
have
is
for
the
pop
operation
to
return
a
slice,
just
a
bite
slice,
a
reference
to
this
particular
section,
which
has
data
to
be
read-
and
this
is
almost
perfect,
except
rebound
the
lifetime
here
to
the
consumer
Itself
by
the
way,
all
of
those
are
associated
functions
in
the
consumer,
struct,
so
yeah.
The
problem
is
because
we
bound
a
lifetime
to
it.
A
We
can
only
really
we
basically
need
to
hold
on
to
this
right
slice
until
the
end
of
the
consumer,
which
means
this
is
at
the
time
where
you
deallocate
the
structure,
and
this
is
quite
useless.
You
need
to,
after
being
done
with
reading
this
data,
somehow
tell
the
consumer
okay
I'm
done
now
increment.
The
tail
atomically
I
don't
need
the
data
anymore,
and
this
is
exactly
where
this
raii
pattern
helps.
A
So
one
thing
you
can
do
is
you
can
wrap
the
like
the
return
type
instead
of
having
a
like
a
reference
into
a
buffer.
Like
a
sorry,
a
reference
of
a
byte
slice,
you
have
a
new
type
in
which
you
include
this
byte
slice,
but
you
implement
a
custom
drop.
Handler
in
this
is
something
I
would
call
section,
for
instance,
so
it
points
to
a
particular
part
of
your
of
this
shared
queue
and
after
you,
after
you,
basically
drop
the
section
object,
then
the
custom
drop
Handler
runs
which
atomically
increments
the
tail.
A
So
this
is
a
way
to
claim
transient,
like
very
short
term
ownership
over
a
certain
part
of
this
byte,
like
this
big
backing
array
and
then
just
give
it
away
again
by
using
this
drop
hander,
and
so
this
is
one
example
of
how
it
would,
for
instance,
look
like
in
my
queue,
so
you
have
a
the
first
year.
First,
the
first
line
you
allocate
a
queue,
the
second
line
you
push
data
to
it
on
the
third
line.
A
It
becomes
interesting,
you
open
a
scope
and
in
this
scope
you
create
this
section
by
popping
off
parts
of
this
by
letting
the
consumer
pop
off
a
part
of
the
skew,
and
now
you
can
actually
take
the
section
which
is
just
a
basically
has
just
holds
a
reference
to
a
bite
slice,
and
then
you
just
iterate
over
it,
and
here
you
can
do
anything.
You
can
also
copy
it.
If
you
want,
you
can
just
perform
a
clone.
Well,
you
iterate
over
it
and
do
some
kind
of
transformation.
A
And
afterwards,
when
you
leave
the
scope,
it
gets
dropped.
So
then
the
tail
gets
atomically,
updated
and
yeah.
This
type
of
pattern
is
very
common,
also
in
C
plus.
So
this
is
not
too
rest
specific,
but
it's
very
practical,
because
this
is
also
how
often
times
you
will
clean
up
mutex
or
mutexes
or
mutex
guards,
or
any
kind
of
lock
guards
or
file
handlers.
A
We
pass
in
a
mutable
reference
of
our
consumer
and
then
what
happens
is
that
we
at
this
point
have
two
overlapping
lifetime
regions
that
both
have
a
mutable
reference
to
the
consumer.
So
this
gets
rejected
by
the
borrower
Checker.
So
we
can't
yeah.
If
this
was
allowed,
we
would
create
horrible
data
races
and
this
would
not
be
safe
to
use,
but
rest
protects
us
from
that,
because
we
can
use
mutable
references.
A
A
Yes,
yes,
exactly
right,
so
I
have
this
big
score,
but
unfortunately,
actually,
fortunately
a
lifetimes
are
not
restricted
by
scope.
We
have
this
nll,
but
so
I
added
this
black
box
here
that
we
forced
the
first
section
to
have
the
lifetime
across
this
whole
scope.
This
is
important
yeah.
Actually,
this
would
be
safe
to
use
if
I
didn't
use
this
section
at
the
bottom
again.
A
Okay,
with
this
in
mind,
so
just
think
a
bit
back.
We
had
a
look
at
some
optimizations
memory
model.
The
thing
is
even
with
those
in
mind,
even
if
you
know
what
you're
doing
it,
it
still
might
happen
that
you
cause
some
kind
of
undefined
Behavior,
because
you're
just
thinking,
programming
mistakes
and
even
the
Border
Checker
can
help
you
with
that.
So
runtime
analysis,
absolutely
yeah.
A
It
is
not
considered
zeroing
The
Producers,
causing
the
user
to
not
be
a
valid
object
right.
So
so,
being
cognizant
of
your
semantics
of
the
invariants
that
certain
objects
have
to
uphold
is
very
important.
The
other
thing
is
dangling
pointers
so
because
it's
a
ring
buffer,
if
I
want
to
push
lots
of
elements,
I
have
to
maybe
perform
a
splitting
mem
copy.
A
I
have
to
do
two
mem
copies
one
at
the
end
of
the
queue
and
one
at
the
start,
and
so
here
this
is
like
one
downside
of
the
constant
generics,
and
basically
this
was
the
code.
This
was
my
first
main
copy
in
my
second
mem
copy
and
the
second
one
I
like
these
two
terms
have
to
be
equal,
but
there
was
a
c
instead
of
an
L
which
blew
up.
So
this
is
something
that
nearly
protected
me
from,
which
is
very
valuable.
A
This
is
very
hard
to
spot
and
the
other
thing
is
something
that
I'm
sure
all
of
you
are
familiar
with.
It's
called
the
racy
and
perfectly
overlapping
Atomic
axis
violation.
It's
like
one
of
the
classic
errors
that
you
find
every
day,
I
think
looking
through
the
audience.
Some
of
you
are
looking
like
this.
A
Okay,
all
right
right.
So
basically,
I
would
like
to
make
some
key
observations,
and
that
is
that
first,
you
should
be
cognizant
of
the
language's
semantic
model.
Basically,
when
you
develop
a
special
concurrent
code,
you
should
know
if
you're
developing
against
a
certain
compute
architecture
or,
if
you're,
using
the
language
semantics
to
develop
against
those
to
create
portable
code.
If
you
do
create
portable
code,
you're
generally
not
allowed
to
rely
on
undefined
Behavior.
A
If
you
do
want
to
rely
on
undefined
Behavior,
then
you
need
to
pin
the
compiler
version,
which
most
people
don't
want
to
do
so
yeah
and
there's
also
another
thing
hidden
here,
which
is
that
in
in
safe
rust,
you
have
lots
of
guarantees
that
you
might
sometimes
maybe
take
for
granted.
So
things
that
go
Way
Beyond
the
shared
sore
mutable
idea
of
the
board
Checker,
because
you
have
like
safe
transmute
rules,
drop
checking.
A
You
have
you
have
this
shared
aliasing
models
stack
borrows
pointer,
provenance,
yeah,
many
things
that
and
also
the
memory
model
which
is
unspecified.
So
there
are
many
of
these
foot
guns
which
makes
unsafe.
Sometimes
many
people
say
that
it's
much
harder
to
write
and
see
so
the
Nomicon
is
actually
a
really
good
starting
point,
because
it
will
lead
you
to
all
the
ways
in
which
you
can
like
write
better
and
save
code
and
writing.
A
A
You
should
be
just
aware
that
maybe
you
might
have
some
presuppositions
about
how
memory
works,
for
instance,
thinking
about
in
terms
of
order
dependencies
or
address
dependencies
when
you're
writing
code
is
actually
one
of
these
foot
guns
that
you
might
not
realize
which
I
didn't
and
lifetimes
you
can
use
them
to
create
save
view
types
so
a
lot
of
times.
You
will
see
a
pattern
where
you
create
a
huge
allocation,
blob
blog
and
then
derive
yeah.
A
Basically,
all
of
these
kinds
of
handlers
that
somehow
Point
into
it
and
then
you
have
all
kinds
of
cleanup
logic
in
drop
handlers
and
that
will
protect
you
in
this
case.
I
would
actually
say
memory.
Waste
is
a
powerful
trade-off.
So
there
is
certain
instances
of
memory,
waste
or
fragmentation
that
I
made
use
of.
First,
all
of
our
producers
have
a
fixed
size.
So
a
lot
of
times,
depending
on
your
workload,
you
have
to
choose
the
size
that
is
very
large,
so
and
oftentimes.
A
You
need
to
waste
space
just
to
accommodate
this
case
of
your
cues
filling
up,
because
you
don't
want
to
have
this
fail
on
overflow
Behavior.
Another
thing
is
that
all
of
The
Producers
have
the
same
size.
They
can't
grow,
which
only
makes
sense
if
you
have
homogeneous
utilization.
Another
thing
is
pointer
compression
where
you
have
like
you,
reduce
the
addressing
granularity
of
your
queue,
but
thereby
wasting
a
bit
of
space,
because
the
queue
can
be
filled
at
100,
and
another
thing
is
actually.
This
is
very
practical
and
switch
like
control
flow
things.
A
This
is
very
practical
for
compilers.
If
you
have
certain
routines-
and
you
have
the
switch
and
all
of
these
subroutines
have
a
fixed
size
that
or
a
bounded
size,
you
can
actually,
they
actually
create
a
hard-coded
jump
table
that
doesn't
cause
any
cache
Miss,
and
this
is
very
practical
for
creating
interrupt
vectored
interrupts
if
you
don't
have
a
vectored
interrupt
support
on
your
architecture
for
some
reason.
A
So
this
is
great
and
if
you
do
have
something
interesting
that
you
learned
then
by
all
means
shared
because
that's
how
we
as
a
community
become
better
at
writing
code,
and
this
is
my
last
recommendation.
This
is
a
guy
called
John
I'm,
not
going
to
butcher
his
name,
and
he
has
a
great
video
on
memory.
Orderings,
so
I
highly
recommend
it
thanks
for
watching.
A
A
Basically,
I'm
writing
a
bare
metal
operating
system
and
he
basically
it's
Unicorno
and
I-
want
to
write
it
specifically
targeted
for
Server
architecture,
but
now
that
nowadays
we
don't
have
risk
5
servers
yet
like
proper
high
performance
course.
But
you
know,
maybe
in
five
years
or
something
so
basically
I'm
preparing.
For
this
event,.
A
I
was
wondering
about
this
alphar
architecture,
which
is
very
relaxed.
The
requirements
is
there
anyway
for
you
to
like
simulate
this
architecture
or
with
Miri
kind
of
catch
ings.
That's
a
good
question
so
for
the
alpha
I,
don't
think
so,
but
we
Miri
does
have
a
weak
memory
model
emulation
and
actually
what
they
do
is
yeah,
basically
they're
emulating
a
weak
memory
model
and
they're
using
all
kinds
of
supportive
structures
to
enforce
that.
A
So
you
actually
would
be
benefiting
a
lot
by
just
running
the
Miri
and
not
so
much
as
running
it
on
maybe
like
an
embedded
system
that
is
has
a
weaker
memory
model
in
this
case,
I
actually
recommend
Miri,
but
it's
very
slow.
So
you
need
to
have
benchmarks
that
really
like
are
able
to
perform
enough
work
for
it
to
catch
it
down.
A
Because
they're
do
you
think
it
would
be
useful
to
encode
the
file
and
the
line
location
in
the
message?
So,
instead
of
sending
the
messages
and
files,
let's
say
ID
and
the
line
ID
entity
to
reduce
the
traffic
like
making
sure
the
messages
are
small
and
concise,
yeah
for
sure
I
mean
yeah,
although,
like
it
depends
in
some
cases,
maybe
you're
debugging
Dynamic
data
that
you
need
to
output
and
and.
A
A
A
This
is
actually
that
it's,
it
makes
no
sense
to
reorder
instruction
or
is
it
is
I
mean
you
could
make
the
argument
that
what
the
alpha
is
doing
is
also
doesn't
make
much
sense,
but
yeah
technically,
you
can
reorder
anything
yeah.
Yes,
yes,
basically,
because,
because,
like
the
reordering
mostly
refers
to
like
how
how
other
processes
in
the
multi-core
system
are
looking
at
the
certain
operations
from
the
outside
so
yeah,
basically,
all
of
these
things
are
documenting.
A
What
kind
of
states
are
observable
for
an
outside
viewer
and
in
many
cases
what
is
observable
is
complete
nonsense,
so
in
that
sense,
yeah
I
think
that
is
possible,
but
I
actually
don't
know
if
this
has
ever
been
done,
but
the
reference
McKinney
is
called
is
parallel
programming
hard
and
if
so,
what
can
we
do
about
it?
It's
a
it's,
a
great
summary
of
all
kinds
of
the
stuff,
and
you
will
find
more
information
there
I
highly
recommend
it.