Player is loading...
Immutable Sequential Maps – Keeping order while hashed
Odd Möller
Thursday, June 13, 2019 · 4:45 p.m. · 46m 05s
A deep dive into the challenges faced when developing and optimizing `immutable.TreeSeqMap` for inclusion into the Scala 2.13 library. See how JMH was used to compare the performance of different `immutable.SeqMap` implementations and the steps followed to improve both performance and memory usage. Which are the trade-offs that need to be considered when choosing between them? Which operations should be avoided and why? How do the immutable implementations compare to the mutable ones? How does the process of contributing code to Scala work? Required Knowledge: Familiarity with Scala and the collections library. Odd is a lifelong coder who got started by hogging his mothers Pascal books and his fathers MacPlus in the mid 80's. After having left university in the late 90's he continued by spending years in the Java Enterprise Factory. Then in 2008 he found the promised land in the form of Scala and have been living there ever since. Now after over ten years as a happy user, he has promised himself to start contributing back more to the community, `TreeSeqMap` being his first larger contribution to Scala.
Embed
Transcriptions
Note: this content has been automatically generated.
00:00:00
yes hi everybody was still here this late in the day i'm gonna speak
00:00:07
about a new kind of map can you type collection and the two thirteen
00:00:14
uh it's i mean it's sequential maps so there um
00:00:19
but i'm gonna focus on the immutable ones but there are also a mutable
00:00:23
one mutable uh implementation yeah and it's yeah that the channel
00:00:28
with those kind of maps is that you wanna keep the order
00:00:32
was still using it uh basically using your hash map which is
00:00:36
not order so that's the the what you're trying to to saul
00:00:42
yeah so we're gonna look a bit about the first introduction then we go through through the challenges
00:00:48
they're gonna look at some of the implementations both the lawns
00:00:51
in b. two thirteen but also and a set of other
00:00:56
possible implementations uh because there are quite a few way or ways
00:01:00
of implementing especially the mutable one's gonna look a little bit about
00:01:05
how you can benchmark these kinds of um implementations against each
00:01:10
other and also which tools to use or which i used anyway
00:01:14
and i uh have a look at the results see what came up the benchmarking
00:01:20
and also a bit about how how does too stark and should be doing to scholars specially yeah yep
00:01:29
i saw um my name is all mahler i'm from
00:01:32
a sweden stock all i've been using a scholar since
00:01:37
i don't remember really year but was version two seven five i think so it's over ten years now uh
00:01:45
yeah and again coding since since forever almost so uh
00:01:49
but not the last ten years almost exclusively in style
00:01:55
so what is a sequential map yeah it's a new types
00:01:59
added into thirteen and it's an interface or trait called seek map
00:02:03
and it's but excess both as a general type and also it's uh
00:02:08
uh like one mutable version and one immutable version as is common in the in the collections library in general
00:02:16
it's like a regular map but the entries or ordered by insertion
00:02:21
and not shorten so so it's the basically the the way the
00:02:27
the yeah the the series of events that you put stuff in the they remain in the same order
00:02:34
uh so no external ordered function is needed so you don't have to
00:02:38
have an ordering the you would raise is based on the operations you perform
00:02:43
and there are yeah po mo mutable and immutable variant
00:02:48
uh even though see map is a new trait in uh
00:02:52
there have been a couple of implementations round for for quite awhile uh in in scholars we'll see
00:02:59
uh so what are you working use them for well any time you need the entries of a map
00:03:06
to have a stable ordering so you want them to to remain in the what are you you insert them
00:03:12
regardless of like if you restart approach program or whatever
00:03:15
you still wanna have a like a defined order and
00:03:20
we like a hash map it can be rewarded on each we started it so it's very unstable but this one is stable
00:03:26
uh and you could uh percent hierarchical data such as j.
00:03:30
some indication isn't order but it's still nice to have it ordered
00:03:34
uh or x. m. our our other stuff and you can also use them for keeping like
00:03:39
you want to map that's maybe files and items or entries
00:03:42
long anyone remove the oldest one you you have all the time
00:03:49
so today we'll look at some different ways to implement to seek map
00:03:53
look at their internal structure a little bit look at it she
00:03:57
to yeah they benchmarking results for some of the more important operations
00:04:02
yeah yeah we'll see what how they differ performance wise
00:04:07
for those operations and also a little bit about memory usage
00:04:12
and hopefully you'll get an understanding of the trade offs between the
00:04:15
difference different implementations so so you can say we went to use which
00:04:22
yeah and of course there's challenges with the with the especially the mutable aunts and that
00:04:29
the basic thing with the sick map is that it's it it
00:04:32
fulfils two separate roles it's a mapping when used to t. based operations
00:04:38
of such look up and all the stuff and it's also wondering so
00:04:42
there's an index based mechanism to to look up or iterate through something
00:04:48
yeah that's yeah so do you need to fulfil both those uh roles
00:04:53
an optimal implementation we have a single representation for both those
00:04:57
of course and while still having the best possible or at least uh
00:05:02
so far and complexity for both those cases but that's really hard to get
00:05:08
uh unless you are willing to trade lots of memory and in like
00:05:13
double store everything done might you might get close to the to the performance you want
00:05:19
yeah and there's also a different difference here between the mutable one on the new one that's we'll see
00:05:28
saw the the most essential operations for uh for c. map is yeah you have
00:05:33
to i had to be able to add and chris or and they're always attended
00:05:37
um so when you add a new t. value binding if the key
00:05:42
isn't already present in in the now it's always appended at the end um
00:05:48
and when you remove elements it you can remove of course the first one on and so on but you can also remove
00:05:55
likely that could be potentially in the middle of a lot map or
00:06:00
it could be my index like index into it like a seek uh
00:06:06
and retrieval can be done by key of course since it's a map but also by by indexing
00:06:13
uh and all iteration walter versus need to be done it in whatever
00:06:20
so we'll have a look at the different types of uh of uh what implementations
00:06:28
yeah and before we had have to say that there's there's lots of prior or chair
00:06:32
yeah we have some install already and ask of course i has implementations as well as java
00:06:39
yeah the cops and they all have different implementations and all the
00:06:43
ones i'm going through today we'll see that's yeah some of them
00:06:47
they don't all all use the same 'cause it's really
00:06:50
hard to know the these different trade also different implementations
00:06:56
we'll start with the mutable and the yeah that's basically
00:07:00
just one thing cash map uh it's it's a really good
00:07:04
oh look really good as good performance doesn't take that much more memory than
00:07:09
a regular hash map it it's been around since in java since one look for
00:07:15
and i mean scholars since one dot oh that's nice uh at the check that but yeah yeah
00:07:22
and the entries on a link pass platform uh doubly linked list this is mutable you can you can
00:07:29
you can have a doubling plus that's really it it's impossible for eight for in in your little
00:07:34
up for mutable one it's fine and that look up is done the same way as for hash map
00:07:40
but the the entries in the hash map point to each other uh and traverse
00:07:45
uh it's becomes very performance you just follow the next reference to the next entry
00:07:50
and you and you don't even have till you can just such the first
00:07:54
one and then walked the references to the next all the way to the um
00:07:59
if you want to traverse a removal so simple yeah you update the previous next entries
00:08:06
those up though so they probably to each other and you skip the one in the middle
00:08:11
uh and the often fermentation supporters both well the
00:08:15
k. insertion of course but also modification access order
00:08:20
being immutable it can it can update its internal state on access
00:08:25
and then you can use it like a a or least recently used that were cash or something which is common them
00:08:35
d. immutable implementation or the the set of immutable if implementations because
00:08:42
there are several and there's no known perfect strategy so so it's really
00:08:47
you have to make a trade off different traders use different performance so or
00:08:52
memory usage uh and uh as i said it there are very many or
00:08:58
a considerable amount of different and implementations and that exist in these different languages
00:09:04
uh there's one strategy for implementing these kind of sequential maps that are uh
00:09:12
you can see it in several implementations and it that is to
00:09:16
use a hash map for the mapping site you keep key too
00:09:21
so yeah valued maybe with some method data and then you combine that with an ordering or the keys
00:09:28
um that means that you will have a and you will have some chi a certain
00:09:33
amount of the double storage because the keys will be reference from two distinct data structures
00:09:41
one use when you when you traverse and one used when you just want to see them get the values
00:09:48
yeah and for immutable data structures in general trees are
00:09:52
really nice because you can you can make a new
00:09:56
like if you had something you can use almost implied three euro perhaps the entire
00:10:00
three with for the new one so it's not you can reuse a lot of the
00:10:06
the nodes in the tree and this is uh you can to see them and say
00:10:11
one prawns for these two e. this are also a good way of of implementing these
00:10:17
so a couple of definitions people get started i uh i'm gonna use this as names in in
00:10:23
the in the following images so when you see a. b. c. d. it's basically that's see map
00:10:31
and when you see a v. c. d. yet i add that like in e. c. binding on that one
00:10:38
a and a b. d. then you remove the c. binding work t. from the a. b. c. d.
00:10:44
yeah but you get it's and was stopped by list map this is
00:10:48
actually the oldest one in in scholars is it's been since colour one bottle
00:10:53
and the entries so this will form a single interest so it's basically
00:10:57
a list a new list uh you add the entries at they had uh
00:11:03
so so the that the most recently added is at the head of the list uh
00:11:10
this this makes a adding really efficient you just pretend something to a list yeah but it requires
00:11:17
that you root root worse reverse the list before or if we can do anything else anything index paste
00:11:24
so so and i think all the operations you do one on a list not that
00:11:30
can you describe that as a unit in it last decomposition
00:11:35
and they're really slow but it asked disco the composition is fast so if you can make your operation
00:11:41
expressed in terms of of the comes to the composition of in that last then it's gonna be really fast uh
00:11:49
so this is basically a a a list map
00:11:53
so you you used you in this case you add a then you add b. then you
00:11:57
let's see and then you had the or the mapping the to the uh so that that's
00:12:03
it's really simple it's it's a linked list with with both the key in the in the value
00:12:09
uh yeah and and by the way this nice pictures on on on
00:12:14
the on them to use in my presentation or i can recommend that um
00:12:20
it's this ref three it's really nice way of being able to display your data structures
00:12:27
you wanna see how they how they look and they
00:12:30
so um
00:12:32
if you look at edition one of the important operations for for uh for list map we can see
00:12:38
that when we yeah we start with a. b. c. d. as usual here and then we had he
00:12:49
the e. mapping we see that you can reuse the whole list
00:12:53
and just pretend something to them is so that's really really nice
00:12:59
but when we have the removal case here then we have to do a little bit
00:13:03
more so we remove and then we would mean this case remove the c. element or binding
00:13:09
so we the seer is gonna most disappears then we must restructure list all the way this part
00:13:15
can be shared with the restaurants of the a. b. c. d. here's new pointer to this part
00:13:24
uh yeah so so that's list but this is a list maps uh it's quite good in this those cases unless you want
00:13:31
to remove something close to the to the start of lawlessness you had gonna have to reconstruct the list all the way up
00:13:39
yeah and this is one of that that's knew when to thirteen the vector map
00:13:45
it uses a hash map for the mapping and it uses the vector for the ordering
00:13:50
and so the hash map contains not only do the key and
00:13:55
value but also uh the index in the vector for each key
00:13:59
this means that you when you remove something by key or you have to find
00:14:04
which indexes this um located so you can remove it from the word ring as well
00:14:10
uh_huh
00:14:13
and this is also the default implementation oversee map in or immutable seek map into thirteen
00:14:20
uh
00:14:21
it looks like this this is the is a simplified picture to this it
00:14:25
disappear right now so i'm gonna use this form to describe the hash map
00:14:32
this is the the not the correct but in reality this is quite a large
00:14:38
tree like structure for the neural hash map and then you use just because that for many of the all these
00:14:46
implementations they'll use this kind of to make the picture simpler i was the
00:14:50
ah i'm concentrating on the order in part because that's what's gonna differ um
00:14:55
i mean you see the the vector map it has the mapping in the
00:14:58
word ring and in the ordering you have the yeah they're the usual vector
00:15:03
and i have an abbreviated here so in reality did this arrays thirty two elements long
00:15:09
uh so when you have added a. b. c. d. you get a nice uh a.
00:15:13
b. c. d. here and the rest or null or now some this uh along right
00:15:21
so when you have something to to a vector map
00:15:26
uh start with a. b. c. d. there
00:15:30
and we we add the mapping so reuse work
00:15:35
this one will be rubber uh this will be an updated hash map but did was
00:15:40
change or add a node here but i want show that uh said but the vector
00:15:46
it needs to build a new actor because it can't share this park with with the early one
00:15:51
since it's still not the if you have more than thirty two then you could share the
00:15:55
the first part of the vector but in this case you need to build a new vector
00:16:03
and for removal this is an interesting case for for vector map uh
00:16:09
we have the vector here and then when we remove stuff the new
00:16:14
new vector
00:16:16
it will it will it won't screw remove the seat from here you see in
00:16:20
the third position leprosy you won't remove me remove it instead of with that insert a
00:16:27
whom tombstone here that says that you have to skip this
00:16:31
elements keep one element ahead if your index if these three
00:16:35
the reason for that is that if you changed all the
00:16:38
indexes that we've done this park wouldn't be able to share anything
00:16:42
like the the then we would have to have a new we would have
00:16:46
to match the entire nah the hash map because all the indexes would change
00:16:52
so to keep the this part as stable as possible we instead replace the the
00:17:01
d. c. element with the tone tones down here uh
00:17:09
yes so this is when when this project
00:17:13
or during the two thirteen uh work in the collection strum worker for that uh
00:17:20
i initially scrape that this one as a reference implementation because if you think about this problem like from
00:17:26
the start you might imagine that you have the hash map you wanna have this uh a. t. two
00:17:32
in dixon value a mapping so why don't store the keys in in a tree map that's gonna be sore
00:17:38
'cause then you use and or to know that you increase on each insert maybe then you have one wondering
00:17:45
from the orientals to the key so you have the hash map as usual and so i i implemented that anna
00:17:51
talk about having it at like a reference point for benchmarking and so on and
00:17:58
and it basically looks like this it's a it's the same
00:18:03
mapping here sorry happen on more so this is the same same
00:18:14
as bad as all this is the the tree map you know
00:18:18
with the it's a red black tree underneath the immutable three map
00:18:22
uh and here you do you have an or no in these cases been increased
00:18:26
to four to have that node with one lisa the b. and yeah so one
00:18:31
zero is a and number on them be and to see and three d. uh so that's the the layout for
00:18:38
and when you add something to this one you get a new so it it it reduces
00:18:45
the some of the nodes you see the zero hired doesn't doesn't need to create a new one
00:18:50
the rest to greece crates but it can reuse a certain amount of the the
00:18:55
the nodes from the uh the existing ordering so that's nice
00:19:03
and when you remove stuff from this kind of collection is the same so same way so you
00:19:09
can reuse certain nodes here from the new green one can still point to some of the no nodes
00:19:16
so you have to create only those two and the no the presentation appear so it's it's
00:19:23
quite good there uh but the thing is that the tree map isn't optimal for this case
00:19:31
like if you wanna have a uh if you wanna have a mapping from ins
00:19:35
to a tease there's a better collection in the already in this colour and it's the intern up uh
00:19:45
so this one is um you don't need it you only need to send in the the the k. it the
00:19:52
he tied because it's the interest already under student as the the
00:19:57
key yeah so it goes from hints to to to keys or
00:20:02
yeah in this case and it performs quite good for all operations
00:20:07
uh but it ah okay price fifty percent more memory them back to map
00:20:11
so so in this case we trade memory for a little better performance especially in some operations
00:20:17
as we'll see so this three c. map looks like this in memory
00:20:26
this is basically a a a bit try
00:20:33
so it has a prefix this is the these are all the on the
00:20:36
on the bit bit values and the mask and then it says that like
00:20:42
one one branch to the left and one to the to the right and
00:20:45
the cat id be tips or they can be a composite tunnels called bins
00:20:50
so you have the tips with with the values and you've constructed like this and
00:20:55
it's while it has quite a few levels this one which
00:20:58
is why takes more memory it's also a all the branching
00:21:03
can be calculated by simple bit operations on ins so they're
00:21:07
going very fast so that's that's one of the good things
00:21:12
and when you add stuff to this looks like this so this one also uses quite a lot of
00:21:19
the old old tree here to nodes can be reused in the simple case while adding a new one there
00:21:25
and those two in intermediate nodes and we wanna when you remove stuff it's the same
00:21:32
the new one can keep using a lot of the the existing three here
00:21:41
oh and the last implementation we'll we'll talk about is the
00:21:48
choose seek map this isn't in scholar at all all it doesn't existence cost on the library it's just
00:21:55
made for reference or for comparison and this one uses a a hash map katie
00:22:01
from katie keys to values for the mapping and also a queue of the
00:22:05
k. e. t.'s and this is an immutable q. so it's a little bit special
00:22:14
the menu but u. s. a. from list in the back list
00:22:19
and it builds as long as you you're building it it depends here
00:22:23
and then it switches in certain situations and i have the uh and the front
00:22:28
and the back reverses it and then it can start again to to add on
00:22:33
you can read more about this in in the
00:22:37
it's a it's a a non uh increases factory it has written a book about
00:22:41
this kind of data structures and you mentioned it's also call up a banker to few
00:22:47
and the hash map is is still the same there
00:22:52
so when you add something here
00:22:54
yeah you have to use you have to prepare 'em the or the east dependent
00:23:01
so it's a new q. ear but it's yeah the lip this list should be it should have been re used here i don't know why didn't
00:23:09
maybe it's wrong with it how would draw said but but it's in principle should be able to use it
00:23:17
removal is the same so you just remove the c. and you get a new list
00:23:21
now you see it's been switched to the frontier well it was in the back there
00:23:33
and then we have uh another one and this one is a bit special because this isn't a
00:23:37
a a one mapping and another uh ordering this one is that me makes the link hash map
00:23:45
uh and so so so it's only a hash map but instead of having the regular entries
00:23:52
up here it has the uh an entry that's also keeps
00:23:58
the key of the nail the previous and the next entry
00:24:02
so the difference to was new to ones that the new bone has a pointer directed to the
00:24:07
entry so it's just a pointer do reference to to get the next entry and then you can
00:24:13
continue to traverse so whilst this one has the key on the next entry says needs to
00:24:20
go to the top of the the uh thing to hash map and
00:24:24
navigate once more down to the of to find the so the there's
00:24:28
if you travel traverse you have to do lookups for each step while in
00:24:32
the middle one you can just uh the reference the the next pointer if uh
00:24:39
so that's a little bit more costly of course
00:24:43
so you see here that the first key say the last key d. and then it has a
00:24:51
hash map here that has entries where where the value is in the middle and the previous pointer
00:24:59
or the previous sorry the previous key is to the left and the next keys to right
00:25:04
so if you have not reduced gets a special now value there but you hear
00:25:09
see that you go by then it's fine be then you have to go appearance and
00:25:13
and traverse again when you find be uh be use their yeah
00:25:18
you see that the previous entry here's a on the next one is c. sitting open
00:25:23
and this has much looks ordered that is just by coincidence
00:25:28
in this case it's a hash map for and those are ordered
00:25:31
but but in general case this will be not be ordered by
00:25:35
a. b. c. d. though this will be like a hash border so it's complete on predictable
00:25:44
so when you add stuff to this one looks like this so you i see not
00:25:52
that we add the d. and now it came first years of the this this isn't order
00:25:58
but still you have the ace you can go there and it can it can it this one
00:26:03
re uses very also quite a lot of the
00:26:06
previous it's they only need change like the surrounding entries
00:26:11
uh in this case the last one because the the previous last ones need to be uh
00:26:15
replaced and the new last one needs to be added a and when you remove
00:26:23
stuff here it's the same same basic thing you see the cherry use much of the
00:26:30
previous note or the earlier novels while while changing so it gets
00:26:36
a new last ones or is actually looks wrong a fixed up
00:26:47
alright if you so
00:26:50
i hope you got a a little bit of an understanding of the the uh how d. b.
00:26:55
different invitations are built up and we'll gonna look at how how would a benchmark those
00:27:03
and when you benchmark in school or job or for that matter but
00:27:07
specialise colour uh there's a nice tool called game age java marker benchmark harness
00:27:14
and it helps you is from uh from uh open you to k. it helps you avoid it many
00:27:21
can common pitfalls in benchmarking it's very easy to to
00:27:25
think you're you're right the benchmarking and like mike benchmark
00:27:30
and it might be all optimised away or something if it's too trivial
00:27:34
so some game h. provides you with a would choose to to keep that from happening and also it
00:27:41
because the benchmark so i tend to be pretty small um maybe do nothing
00:27:45
meaningful and then it's easy that to to get lost with the and that the
00:27:51
just in time compiler uh up to my sis away all your or your code almost
00:27:57
and if you're gonna use game age with the with the scholar ah there's a nice beside him
00:28:02
um s. p. t. game game age uh perhaps it makes it very
00:28:08
easy to to run these can a bunch more from from s. p. t.
00:28:13
and there's also a tool called the image visualise or that lets you
00:28:19
drag you drag and drop your or a results file a some file
00:28:25
into the and i will draw all the diagrams and stuff so that's really nice and it also supports if you wanna run
00:28:32
run your benchmarks on say on j. d. k. eight
00:28:35
eleven or with the crawl without crawl those kind of stuff
00:28:41
so this is an example they came h. program or benchmark
00:28:46
uh i don't know if you've you've seen it but it's just like the simplest possible you say your sizes they wanna use
00:28:53
and then you have the subject you wanna just then you initialise
00:28:57
it in a setup meant methods you created of various sizes than
00:29:02
um and then you define your benchmark as a method
00:29:06
like a just reverse iterate or to get a traitor from the subject and then
00:29:11
move through with an down here you have a a black hole at the b. h.
00:29:17
and that makes it that's there for to ensure that the the um you it doesn't all
00:29:24
doesn't uh um you know you see here that we doesn't we don't use the result
00:29:29
of the next year so that could skip potential skip this whole while but by consuming it
00:29:35
we hide from the you what we do with it so it
00:29:37
can't optimise away the the logic yeah and this is the visualise right
00:29:47
i thought i might try to open this
00:29:54
so this is how it looks when you go there you get like a screen and we can or drop area we
00:30:01
can drop their farms singer can start by them in the memory of alright fucking get drag and drop to work on a
00:30:36
it's so then it shows the the with a staple that
00:30:45
diner here you can see that yeah out here is the name
00:30:50
of the the benchmark so this is the implementations where like
00:30:54
healing to seek map vector map you see map and so on
00:30:59
and here we see that for the memory usage in this
00:31:01
case the tree see map is um it's quite but it
00:31:10
is it worth it uses a lot more memory than the other ones like double them amount of memory almost doubles on them
00:31:16
and while the best one seems to be the link links has market dusty
00:31:22
that's the mutable one so that's really good memory wise uh we also see that the
00:31:28
the the important vector map here one of the uh the default implantation that's quite good
00:31:34
memory usage if you hold your mouse or you get like the the actual figures and so on
00:31:42
so that's the memory we can do the same for do the same for some operation injector
00:31:55
what's our results or you can take one lap yeah
00:32:04
and take concatenating to all these arrays or the c. maps
00:32:08
together and look look closer at that operation second that he does
00:32:29
to um how the models
00:32:32
i ah doesn't seem to okay
00:32:43
yeah you can also load stuff from your l. some from gets so you can publish or salsa on the not if you want to
00:32:53
i used this one is done
00:33:01
it's just a moment
00:33:05
time so it's
00:33:12
yeah it's yeah we'll take some yet contract was that the one i wanted
00:33:27
so this is a sample of the contracts it's only for two so i said so there's not not not many
00:33:33
there's only two one six is sixty three elements and one for for tell thousand ninety six elements
00:33:39
here you can see that the the the like the vector market isn't especially good that couldn't get anything hurts
00:33:47
the value there is nine almost a million while uh if you
00:33:51
in the fastest one is to free has seek map it has
00:33:57
like three hundred and seventy thousand and also the g. c. map huh
00:34:01
it's quite a bit faster than rectum apple half less than half
00:34:06
so contact is the one operation where they were there's quite a few
00:34:10
differences but the most most operations are actually almost the same uh independent or
00:34:18
uh which can find oh okay
00:34:27
it's a uh like a pending maybe
00:34:36
so here's the yeah the time it takes to combat these are really slow a really low numbers
00:34:42
so even though they seem to differ quite a bit it's still almost the
00:34:46
same and a and a pending is really fast for almost all of them
00:34:54
i haven't list map is not an including these because if you include this map
00:34:59
on the operations where is not not any good it's so slow that
00:35:03
it's like a skews tickle result you see nothing else except this map
00:35:09
uh so i've excluded from my from my rounds but one instant interesting
00:35:15
one interesting uh salter would that mean loaded where they differ quite a bit
00:35:25
and this is also that the reason that a three c. map is into
00:35:32
that all i think in the in two thirteen fine so in this one
00:35:55
this is if you ah the relevance and then you remove them in the same order you added them then you will
00:36:04
for the vector map you will keep removing indexes after one another in the race you
00:36:09
have to replace those with some stones the point to but when you like when you remove
00:36:16
have many such some stone in role that you need to go lie it's becomes like a linear
00:36:21
opted to change each one of those tones tones to point to the to the next because you
00:36:26
the wonder upon people is now removes you need to update
00:36:28
the pointer one morning increment pointer and that's really really expensive
00:36:34
and so you see that like to map here has almost you go to the logarithmic scale or start
00:36:42
you see that that the the vector my past maybe
00:36:46
yeah for uh for under forty thousand no million and then
00:36:52
you shake the fastest one is um three c. map here and that that one has two two and a half
00:37:00
two point two million so that's quite a quite a gap between those two uh
00:37:06
so so yeah that that's one of the lessons you can learn from from this uh benchmarking results
00:37:12
let's get back to the presentation stay
00:37:20
which yep so
00:37:25
the conclusions what what conclusions can make about these implementations
00:37:29
well i've been on said some of those of this but this map
00:37:34
is really fast for operations based on unit last the consider the composition
00:37:39
so if that's if you know that's what you wanna do you
00:37:41
can keep using list map is actually the best perform in those cases
00:37:46
but it's also released over and anything else uh and that's because it has to reverse
00:37:51
the list on each each operation and that's quite costly if the list is is growing large
00:37:57
three hash see map is simple to implement it's
00:38:01
almost a trivial to implement uh uh but it's also
00:38:06
quite slow and and and memory intensive so so and that's
00:38:11
why uh three seek map is an improvement of that one
00:38:15
vector map is is fast overall it's a
00:38:18
really good choice for everything except consecutive the removals
00:38:22
and so if you remove stuff in the same order you you put it in that it might not be the best the
00:38:28
choice or and the three sick map it's it it's on par
00:38:34
with vector map overall except for move where it's very much faster
00:38:40
so it should be a button it requires fifty percent more memory
00:38:43
than vector map at least the version that's currently in two thirteen does
00:38:48
and there's a i've been working on an improvement that might get that down to twenty percent more something
00:38:55
the killing to see rob is promising but i haven't had the i i. wrist and
00:39:01
add that it's quite recently and so i haven't done the most extensive uh
00:39:06
testing testing on it but it looks quite a quite nice and i i believe that it might be
00:39:13
uh it uh you might be able to make that the the the like a a good
00:39:17
compromise between back to my country seat map uh so it might be the make maybe four votes
00:39:24
futures colour version that will be the ones that i saw doubled basically the stuff i hadn't about
00:39:32
the the implementations i also uh also gonna speak a little bit about how it was to
00:39:38
start contributing because i'm even though i'm uses colour for ten years i haven't been a a contributor
00:39:44
maybe fix some barb or something like that in a few products but i haven't had time to to to contribute more than that
00:39:51
but um but i've been doing that now and it started with the collections dormant project
00:39:59
i don't know if everyone no doubt but that was like a um like a test
00:40:03
ground for a new collections the ones that are now in in two thirteen um and that
00:40:11
i got interested in that one also yeah that's a really nice and what's um
00:40:16
i started developing a collection type there that's like all spam takes a but it it wasn't uh it was like
00:40:23
the receipts that's also a new implementation to thirteen but
00:40:27
it was circular c. could append the as well let's pretend
00:40:30
uh to it and and it had supported right once mutation and which makes
00:40:35
it really good in some cases or or many cases but also have some
00:40:41
uh hard to handle corner cases uh it was i
00:40:44
did not succeed in getting it merged so so um um
00:40:48
it would yeah so i i continued instead because i i'm uh i like the to work on them
00:40:55
for my spare time once colour so i i got interested in the sigma work
00:41:00
initiate promise you the the jewish uh and i wrote this simple
00:41:04
cream of hash map based implementations use as a reference for benchmarking
00:41:09
then i started thinking ways to optimise that implementation and the end up with a three c.
00:41:13
map and that got merged into searching uh uh and this spot community i found was very
00:41:24
very valid welcoming this truman product especially was
00:41:28
a very very nice to to to have a
00:41:32
starting point uh and like to thank you again gently shot for their he did a good
00:41:40
helped helped a lot when you start out and so so uh if
00:41:47
you have a like a a mate maybe those kind of all of
00:41:52
this of the of the side projects are are are good way of
00:41:56
getting new contributors to start contribute to at least with for me because like
00:42:02
instead of getting to know the full scholar it's quite complex with all the the modules and
00:42:07
how the structure in the in the source tree and so on you can start with something smaller
00:42:12
and and grow from there are and i almost got good feedback and advice
00:42:18
on on an ample requests i made a the meeting there's of course there there
00:42:24
often quite busy we're very busy so so the of
00:42:29
course you can't expect immediate feedback but i i yeah
00:42:34
like if you ping them once in a while if you uh that they don't come around
00:42:40
just be nice to them because they have so much to do yeah the the base of it so
00:42:47
i'm thinking about taking some questions
00:42:52
anyone
00:42:53
how
00:43:00
yes and did you explore this idea of that you have like a mutable collection and
00:43:06
then you switch it to be calm immutable like ruby does that is as operation freeze
00:43:12
closure has something room i quite similar where you work with my
00:43:17
mutable thing and then you make it in constant time immutable thank you
00:43:23
yes uh uh yes i uh that's one way to uh
00:43:27
there's just too aspect of that one is that in in
00:43:32
if you have a persisting like a a mutable collection and you can
00:43:39
we have builder since colour and those you can like even for the immutable collections you
00:43:43
can you while you have that builder you you can use mutation and so on in it
00:43:48
in there if it's on the up and on the laying array or something and
00:43:52
then once you call resulted nulls now it's finished so then it can return but then
00:43:57
a common way of working with that will like with the list is that you have a list you can as a pens
00:44:04
an item to it and do the old this is still the valid so
00:44:08
the you don't know they've that's gonna be kept on you you need to
00:44:12
be used to can it if if you have like an an array seek
00:44:16
that's an immutable array you can start even even though they are a mites
00:44:23
allow your re buffer allows that you have it can put stuff in it you
00:44:27
don't know if any of the uh uh anyone has a reference to the old
00:44:32
the old states you need to get that that's that needs to be kept forever basically
00:44:37
um so that that's one thing if if if the a. p. i. installer would have been
00:44:41
more like that you were forced to close some seal method at the end or something
00:44:47
then you might have a that's like the builder result method then you would know that yeah from here on
00:44:52
yeah you can changeable but up here you can when i did the spandex work that actually
00:44:57
shane just behind your back but it only that does so if it knows that no one
00:45:02
no no one else has changed before but once it's changed that's top will never be able to change again
00:45:09
so it's more like a right once uh if uh and and the the bad thing with that is that you
00:45:16
like if someone right has a bigger a and and writes one some something in a free slot and that becomes sealed
00:45:22
then if someone has the rave that hasn't it's sealed that would hasn't sit
00:45:27
like one one step further if they try to write you have to copy the folder rate each
00:45:31
time so that's that's quite expensive and it might be surprising that that i had in one elements
00:45:38
this is a really expensive not as expensive operation um so that's
00:45:42
that's a reason whites didn't get merged i think but thinking good question
00:45:49
i want
00:45:54
right
Conference Program
A Tour of Scala 3
Martin Odersky, Professor EPFL, Co-founder Lightbend
June 11, 2019 · 5:15 p.m.
8337 views
A story of unification: from Apache Spark to MLflow
Reynold Xin, Databricks
June 12, 2019 · 9:15 a.m.
1267 views
In Types We Trust
Bill Venners, Artima, Inc
June 12, 2019 · 10:15 a.m.
1569 views
Creating Native iOS and Android Apps in Scala without tears
Zahari Dichev, Bullet.io
June 12, 2019 · 10:16 a.m.
2232 views
Techniques for Teaching Scala
Noel Welsh, Inner Product and Underscore
June 12, 2019 · 10:17 a.m.
1296 views
Future-proofing Scala: the TASTY intermediate representation
Guillaume Martres, student at EPFL
June 12, 2019 · 10:18 a.m.
1157 views
Metals: rich code editing for Scala in VS Code, Vim, Emacs and beyond
Ólafur Páll Geirsson, Scala Center
June 12, 2019 · 11:15 a.m.
4695 views
Akka Streams to the Extreme
Heiko Seeberger, independent consultant
June 12, 2019 · 11:16 a.m.
1552 views
Scala First: Lessons from 3 student generations
Bjorn Regnell, Lund Univ., Sweden.
June 12, 2019 · 11:17 a.m.
577 views
Cellular Automata: How to become an artist with a few lines
Maciej Gorywoda, Wire, Berlin
June 12, 2019 · 11:18 a.m.
386 views
Why Netflix ❤'s Scala for Machine Learning
Jeremy Smith & Aish, Netflix
June 12, 2019 · 12:15 p.m.
5026 views
Massively Parallel Distributed Scala Compilation... And You!
Stu Hood, Twitter
June 12, 2019 · 12:16 p.m.
958 views
Polymorphism in Scala
Petra Bierleutgeb
June 12, 2019 · 12:17 p.m.
1113 views
sbt core concepts
Eugene Yokota, Scala Team at Lightbend
June 12, 2019 · 12:18 p.m.
1656 views
Double your performance: Scala's missing optimizing compiler
Li Haoyi, author Ammonite, Mill, FastParse, uPickle, and many more.
June 12, 2019 · 2:30 p.m.
837 views
Making Our Future Better
Viktor Klang, Lightbend
June 12, 2019 · 2:31 p.m.
1682 views
Testing in the postapocalyptic future
Daniel Westheide, INNOQ
June 12, 2019 · 2:32 p.m.
498 views
Context Buddy: the tool that knows your code better than you
Krzysztof Romanowski, sphere.it conference
June 12, 2019 · 2:33 p.m.
394 views
The Shape(less) of Type Class Derivation in Scala 3
Miles Sabin, Underscore Consulting
June 12, 2019 · 3:30 p.m.
2321 views
Refactor all the things!
Daniela Sfregola, organizer of the London Scala User Group meetup
June 12, 2019 · 3:31 p.m.
514 views
Integrating Developer Experiences - Build Server Protocol
Justin Kaeser, IntelliJ Scala
June 12, 2019 · 3:32 p.m.
551 views
Managing an Akka Cluster on Kubernetes
Markus Jura, MOIA
June 12, 2019 · 3:33 p.m.
735 views
Serverless Scala - Functions as SuperDuperMicroServices
Josh Suereth, Donna Malayeri & James Ward, Author of Scala In Depth; Google ; Google
June 12, 2019 · 4:45 p.m.
936 views
How are we going to migrate to Scala 3.0, aka Dotty?
Lukas Rytz, Lightbend
June 12, 2019 · 4:46 p.m.
709 views
Concurrent programming in 2019: Akka, Monix or ZIO?
Adam Warski, co-founders of SoftwareMill
June 12, 2019 · 4:47 p.m.
1974 views
ScalaJS and Typescript: an unlikely romance
Jeremy Hughes, Lightbend
June 12, 2019 · 4:48 p.m.
1377 views
Pure Functional Database Programming‚ without JDBC
Rob Norris
June 12, 2019 · 5:45 p.m.
6374 views
Why you need to be reviewing open source code
Gris Cuevas Zambrano & Holden Karau, Google Cloud;
June 12, 2019 · 5:46 p.m.
484 views
Develop seamless web services with Mu
Oli Makhasoeva, 47 Degrees
June 12, 2019 · 5:47 p.m.
785 views
Implementing the Scala 2.13 collections
Stefan Zeiger, Lightbend
June 12, 2019 · 5:48 p.m.
811 views
Introduction to day 2
June 13, 2019 · 9:10 a.m.
250 views
Sustaining open source digital infrastructure
Bogdan Vasilescu, Assistant Professor at Carnegie Mellon University's School of Computer Science, USA
June 13, 2019 · 9:16 a.m.
375 views
Building a Better Scala Community
Kelley Robinson, Developer Evangelist at Twilio
June 13, 2019 · 10:15 a.m.
245 views
Run Scala Faster with GraalVM on any Platform
Vojin Jovanovic, Oracle
June 13, 2019 · 10:16 a.m.
1342 views
ScalaClean - full program static analysis at scale
Rory Graves
June 13, 2019 · 10:17 a.m.
463 views
Flare & Lantern: Accelerators for Spark and Deep Learning
Tiark Rompf, Assistant Professor at Purdue University
June 13, 2019 · 10:18 a.m.
380 views
Metaprogramming in Dotty
Nicolas Stucki, Ph.D. student at LAMP
June 13, 2019 · 11:15 a.m.
1250 views
Fast, Simple Concurrency with Scala Native
Richard Whaling, data engineer based in Chicago
June 13, 2019 · 11:16 a.m.
624 views
Pick your number type with Spire
Denis Rosset, postdoctoral researcher at Perimeter Institute
June 13, 2019 · 11:17 a.m.
245 views
Scala.js and WebAssembly, a tale of the dangers of the sea
Sébastien Doeraene, Executive director of the Scala Center
June 13, 2019 · 11:18 a.m.
661 views
Performance tuning Twitter services with Graal and ML
Chris Thalinger, Twitter
June 13, 2019 · 12:15 p.m.
2003 views
Supporting the Scala Ecosystem: Stories from the Line
Justin Pihony, Lightbend
June 13, 2019 · 12:16 p.m.
163 views
Compiling to preserve our privacy
Manohar Jonnalagedda and Jakob Odersky, Inpher
June 13, 2019 · 12:17 p.m.
301 views
Building Scala with Bazel
Natan Silnitsky, wix.com
June 13, 2019 · 12:18 p.m.
565 views
Diversity and Inclusion Panel: Bring the Thunder!
Panel
June 13, 2019 · 2:30 p.m.
244 views
Asynchronous streams in direct style with and without macros
Philipp Haller, KTH Royal Institute of Technology in Stockholm
June 13, 2019 · 3:45 p.m.
304 views
Interactive Computing with Jupyter and Almond
Sören Brunk, USU Software AG
June 13, 2019 · 3:46 p.m.
681 views
Scala best practices I wish someone'd told me about
Nicolas Rinaudo, CTO of Besedo
June 13, 2019 · 3:47 p.m.
2706 views
High performance Privacy By Design using Matryoshka & Spark
Wiem Zine El Abidine and Olivier Girardot, Scala Backend Developer at MOIA / co-founder of Lateral Thoughts
June 13, 2019 · 3:48 p.m.
754 views
Immutable Sequential Maps – Keeping order while hashed
Odd Möller
June 13, 2019 · 4:45 p.m.
277 views
All the fancy things flexible dependency management can do
Alexandre Archambault, engineer at the Scala Center
June 13, 2019 · 4:46 p.m.
389 views
ScalaWebTest - integration testing made easy
Dani Rey, Unic AG
June 13, 2019 · 4:47 p.m.
468 views
Mellite: An Integrated Development Environment for Sound
Hanns Holger Rutz, Institute of Electronic Music and Acoustics (IEM), Graz
June 13, 2019 · 4:48 p.m.
213 views
Closing panel
Panel
June 13, 2019 · 5:54 p.m.
400 views