https://kotlinlang.org logo
#coroutines
Title
# coroutines
c

Colton Idle

08/07/2022, 1:21 AM
This is potentially something that should just go into #getting-started but I'll just ask here. I have a list that I search through and while I search through it, sometimes the list is updated. No issues, except for that the list is large and so it's "slow" and lags the UI. I wrapped it in a
withContext(Dispatchers.Default){
but now I get a
ConcurrentModificationException
. I could understand if I was adding/removing to the list on Dispatchers.Default while main thread was swapping the list entirely... but I'm just searching via
indexOfFirst
. thoughts?
e

ephemient

08/07/2022, 1:28 AM
regarding the default Java ArrayList implementation: it is not safe for concurrent read/write. all iterators are invalidated on any structural change.
is your indexOfFirst running in a different thread than the mutations? if so, CME is expected
c

Colton Idle

08/07/2022, 1:30 AM
Interesting. So I thought ConcurrentModException was multiple updates by different threads. but if my indexOfFirst is running in Dispatchers.Default, and so it's reading, while someone else is writing, then i guess it makes sense
the conccurent "modification" part threw me off I suppose. because i didn't think reading was a 'modification'
e

ephemient

08/07/2022, 1:30 AM
it's not
but another concurrent modification while you are reading is CME
c

Colton Idle

08/07/2022, 1:33 AM
Okay. Hm. not sure how to solve this then. Doing this search is taking a long time, so I tried to just wrap it in a withContext(Dispatchers.Default)
Copy code
val indexOfPlace = appState.fullList.indexOfFirst { it.id == placeUid }
but it led to the CME. I wonder what the best thing to do here is. I really didn't think that reading a list while it's being modified would cause an issue.
e

ephemient

08/07/2022, 1:35 AM
it is an issue - list has no synchronization so any structural change can lead to an inconsistent read on another thread (imagine if elements are being shifted or the underlying array is reallocated)
c

Colton Idle

08/07/2022, 1:36 AM
Gotcha. Okay I'm gonna rethink my approach.
thank you @ephemient
e

ephemient

08/07/2022, 1:39 AM
there are some (possible expensive) alternatives such as never modifying a list and publishing a new one on change, or using
CopyOnWriteArrayList
which (as the name implies) creates a copy on every modification, so existing iterators are not invalidated (although they will continue operating on a stale copy)
c

Colton Idle

08/07/2022, 1:56 AM
Gotcha. I'm not exactly sure how to proceed because basically the setup I have is that there are 10 items in a list. When a user selects an item, a long running operation happens and at the end of the operation, the original item in the list is updated. My issue shows up when a user clicks item 1, item 1 begins processing, then user selects item 2. It seems like I could try to cancel job 1 when user clicks item 2, but the info from job 1 is still valid and so having that job finish would be preffered.
Pruned down my issue from like 1000 lines of code to just this. Curious if you have a clue @ephemient? https://stackoverflow.com/questions/73300823/kotlin-concurrentmodificationexception-when-searching-a-compose-snapshot-state
e

ephemient

08/11/2022, 1:07 AM
yeah that's just not safe, regardless of Compose. you can only read a data structure in multiple threads if it's immutable or if it's known to be thread-safe (which List isn't)
(I've also taken the liberty of using a
Map
to eliminate the need to scan with
indexOfFirst
for each item)
c

Colton Idle

08/11/2022, 2:28 AM
you can only read a data structure in multiple threads if it's immutable or if it's known to be thread-safe (which List isn't)
TIL. I thought that you can red a data structure in multiple threads if you basically know when each thread is calling which. which in this case I thought that'd be safe because even though im switching threads, im trying to be procedural about the whole thing.
if you can make
appState.fullListOfTodos
into a
MutableState<List<Model>>
, then that is safe to update from other threads.
okay. that makes sense. So the list is immutable, but I can change the list that I'm referencing overall from other threads?
then you just keep everything else immutable, and process all the mutation on a single thread
wait. so doesn't this just go against what you just said of "then that is safe to update from other threads."
(I've also taken the liberty of using a
Map
to eliminate the need to scan with
indexOfFirst
for each item)
yeah. I was definitely getting to the point where I wanted to use a map. but as an excercise I wanted to see how I can do this performantly with just a list. as my crux of the issue has been that indexOfFirst is slow (of course) with a large list, and so I was like "oh wait. coroutines makes this a piece of cake"
e

ephemient

08/11/2022, 2:50 AM
the list is immutable, we're replacing the reference with a different list on update
c

Colton Idle

08/11/2022, 2:55 AM
gotcha. so just technically speaking. i'm working around the issue by having a duplicate list (i.e. twice the memory used). right? am i following that?
if so. then yeah. that makes sense.
e

ephemient

08/11/2022, 2:57 AM
well, sorta - there's both a map and list representation in there, which takes more space, but they are holding references to the same models, so if there's few changes then there's not that much allocation
to give a simpler example,
Copy code
List(100) { SomeBigObject() }.toList()
results in two lists (at least temporarily), each with a backing array of size (at least) 100, but there's only 100
SomeBigObject
instances across them
c

Colton Idle

08/11/2022, 3:03 AM
esults in two lists (at least temporarily), each with a backing array of size (at least) 100, but there's only 100
SomeBigObject
instances across them
🤯 why hasn't that occurred to me? lol. okay cool. wow. so many TILs.
in a bit im going to try to redo my code from the stackoverflow question with your suggesstion of "if you can make
appState.fullListOfTodos
into a
MutableState<List<Model>>
" I really like your solution you outlined here BUT out of curiosity I just want to see if I can make my current code not crash
But the code that you have of having a Flowable of requests is where i was thinking i should end up so thats nice to see that you opted for that as well.
okay. it seems like its not crashing with this change. This is what I did 1. Changed to
appState.fullListOfTodos
into a
MutableState<List<Model>>
2. Switched
Copy code
//this search for index could take a long time, so move to CPU bound Dispatcher
                withContext(Dispatchers.Default) {
                

                  // The crash/exception happens on this line VVV
                  indexOfTodo =
                    appState.fullListOfTodos.indexOfFirst { it.id == todo.id }
                  place = appState.fullListOfTodos[indexOfTodo]

                  updatedTodo = TodoModel(//update a few fields)

                }
                // If I remove this line, the crash/exception does not happen VV
                appState.fullListOfTodos[indexOfTodo] = updatedTodo
to
Copy code
withContext(Dispatchers.Default) {
                
                  indexOfTodo =
                    appState.fullListOfTodos.indexOfFirst { it.id == todo.id }
                  place = appState.fullListOfTodos[indexOfTodo]

                  updatedTodo = TodoModel(//update a few fields)

                  val newList = appState.fullListOfTodos.toMutableList().apply { this[indexOfTodo] = updatedTodo }
                  appState.fullListOfTodos = newList
                }
How does that sound to you? (again with the premise that I will be updating my code to your other suggestion i.e. Flowable and using a Map) but if I wanted to "solve" this just as practice then I think this makes sense...
Oh. another option I just thought of... just keep my code identical but only change this line.
Copy code
indexOfTodo = appState.fullListOfTodos.indexOfFirst { it.id == todo.id }
to
Copy code
indexOfTodo = appState.fullListOfTodos.toList().indexOfFirst { it.id == todo.id }
I think i might like that change the best for now as basically i just create another list (but reuse the todos inside the list) to perform the query on a background thread, and then still manipulate the original list on the main thread.
e

ephemient

08/11/2022, 4:52 AM
.toList()
there doesn't make a difference. it creates another copy, but that requires iterating and reading the list just the same as
.indexOfFirst
does, and will fail if the list is concurrently mutated
either your list isn't being concurrently mutated (in which case both
.toList().indexOfFirst {...}
and
.indexOfFirst {...}
are safe), or your list is being concurrently mutated (in which case both
.toList().indexOfFirst {...}
and
.indexOfFirst {...}
are unsafe). if anything,
.toList
has about a double chance of being unsafe on average, since it always iterates the whole list instead of stopping when
.indexOfFirst
finds the first match (assuming random distribution)
c

Colton Idle

08/11/2022, 6:09 AM
.toList()
there doesn't make a difference. it creates another copy, but that requires iterating and reading the list just the same as
.indexOfFirst
does, and will fail if the list is concurrently mutated
damn. maybe its just happening so quickly that its not triggering a CME in my testing. thanks for the heads up on that.
either your list isn't being concurrently mutated
in my original SO question I still don't see how it's being concurrently mutated honestly.
I understand that I'm searching through the list on Dispatchers.Default, and then inserting on Main... but these happen procedurally... and so I don't see what's "concurrent" about it.
e

ephemient

08/11/2022, 6:48 AM
cancellation isn't immediate
in particular, if the coroutine is running a block of compute code with no suspend points, it will not be cancelled
c

Colton Idle

08/11/2022, 6:53 AM
gotcha. so the thing that's breaking my "logic" here is that im assuming cancellation is immediate. whoa boy. okay. your solution DEFINITELY sounds like the way to go then.
e

ephemient

08/11/2022, 6:55 AM
to clarify, it will be cancelled… eventually. it just won't be observed until it hits a suspend point
c

Colton Idle

08/11/2022, 6:55 AM
so ill just ask one more time here. My current code (as posted on stackoverflow). What's the minimal amount of change to get that working? It'd be this, right? 1. Change to
appState.fullListOfTodos
into a
MutableState<List<Model>>
2. Switch
Copy code
//this search for index could take a long time, so move to CPU bound Dispatcher
                withContext(Dispatchers.Default) {
                

                  // The crash/exception happens on this line VVV
                  indexOfTodo =
                    appState.fullListOfTodos.indexOfFirst { it.id == todo.id }
                  place = appState.fullListOfTodos[indexOfTodo]

                  updatedTodo = TodoModel(//update a few fields)

                }
                // If I remove this line, the crash/exception does not happen VV
                appState.fullListOfTodos[indexOfTodo] = updatedTodo
to
Copy code
withContext(Dispatchers.Default) {
                
                  indexOfTodo =
                    appState.fullListOfTodos.indexOfFirst { it.id == todo.id }
                  place = appState.fullListOfTodos[indexOfTodo]

                  updatedTodo = TodoModel(//update a few fields)

                  val newList = appState.fullListOfTodos.toMutableList().apply { this[indexOfTodo] = updatedTodo }
                  appState.fullListOfTodos = newList
                }
e

ephemient

08/11/2022, 6:59 AM
what is appState.fullListOfTodos? if it's not some sort of atomic reference then it's not necessarily safe (although it likely is ok in practice)
if it's not atomic and there's no other synchronization involved, it is possible for the list reference update to be published before the updated contents of that list are published to memory
kotlinx.coroutines does ensure a happens-before relation between every suspend point but as we pointed out above, your problem occurs outside of that
tl;dr I recommend to stop trying to cheat at concurrency. just do it the right way
c

Colton Idle

08/11/2022, 7:34 AM
Agree with what you're saying. I guess I'm just moreso thinking "if Flows didn't exist, how would I do this. Should I just change my underlying data structure? etc" but yeah. ive learned so much with this. I can't believe its taken me so long to encounter a problem like this but i think its mostly due to the fact that ive probably dont crude searches like this on the main thread in the past... but now I have a pretty damn huge list so I was like "i know. ill just move it to dispatchers.Default" and im just in a world of pain because of that choice now. And so while I 100% agree that I should change my approach here, I am just curious if I can take my "working but slow" main thread approach and "easily" throw it onto a background thread.
i guess "easily throw it onto a background thread" is just not really a thing as it requires a good amount of thought to make sure that im using the right underlying datastructures, etc.
this is probably a dumb question too... but do you know if theres any sort of strict mode or something that i can enable so i can find CMEs faster than just trying to mash on the refresh button in my app? lol i feel like itd be easier to for me to learn whats really going on if it was a bit more deterministic over what was happening.
e

ephemient

08/11/2022, 8:05 AM
unfortunately not as far as I know, I feel like it would be difficult to do in Java
c

Colton Idle

08/11/2022, 8:10 AM
gotcha. well. this was a whirlwind tour on things i thought i knew but I guess i didn't. i thought mutableState* in compose was actually immutable (adam powell once said that mutableState is actually imutable with a mutable facade) and so i thought that id be able to just update that whereever i please. i still dont get the coroutine cancellation isn't instant/immediate thing, but i will read into that as well. You solution of using a flow and a map is what I want to move to, but you use a bunch of apis there that I want to read about first before just converting my app to it (ie. folding, etc) Thanks @ephemient!!!! ❤️ ❤️ ❤️
e

ephemient

08/11/2022, 8:10 AM
looks like there's a proposal: https://openjdk.org/jeps/8208520
no implementation that I can find though
yeah you don't necessarily need to use Flow - the core idea is just that you're safe if mutable objects are all either protected by synchronization or local to a single thread (or coroutine), and everything else that is shared between threads (or coroutines) is immutable
(or only just the main thread which effectively sequentializes all operations, I suppose)
oh there is an implemention, https://wiki.openjdk.org/display/tsan/Main . hasn't been updated in a couple years which seems concerning
c

Colton Idle

08/11/2022, 8:31 AM
that IS cool. but yeah. a bit of a bummer that its been a few years. way to go finding it. I also think your last tldr of it makes a lot of sense to me.
will still need to re-read your impl because I'm not sure what strategy your impl necessarily takes off the cuff. theres a lot going on there. but since you're flowing on Dispatchers.Default then I suppose you're just going the immutable route.
Things in your solution I've never used before MutableSharedFlow, accumulator, runningFold, toMutableMap, copyFromItem, launchIn, 😂 😭
e

ephemient

08/11/2022, 12:24 PM
copyFromItem and toModel aren't standard things, fill those in with your real implementation
c

Colton Idle

08/11/2022, 12:26 PM
Oh. Lmao
e

ephemient

08/11/2022, 12:32 PM
Copy code
someFlow.runningFold(initial, transform)
is short for
Copy code
flow {
    var accumulator = initial
    emit(accumulator)
    someFlow.collect { value ->
        accumulator = transform(accumulator, value)
        emit(accumulator)
    }
}
same as the Iterable extension by the same name
Copy code
someFlow.launchIn(scope)
is short for
Copy code
scope.launch {
    someFlow.collect()
}
c

Colton Idle

08/11/2022, 12:35 PM
gotcha. I see launchIn and run because of this article. although I admittedly dont really understand it. ive just avoided it all this time since adam powell said this article was good https://www.billjings.net/posts/title/avoid-launchin/?up=technical
7 Views