https://kotlinlang.org logo
Join Slack
Powered by
This is potentially something that should just go ...
# coroutines
c
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
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
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
it's not
but another concurrent modification while you are reading is CME
c
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
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
Gotcha. Okay I'm gonna rethink my approach.
thank you @ephemient
e
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
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
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
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
the list is immutable, we're replacing the reference with a different list on update
c
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
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
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
.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
.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
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
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
to clarify, it will be cancelled… eventually. it just won't be observed until it hits a suspend point
c
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
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
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
unfortunately not as far as I know, I feel like it would be difficult to do in Java
c
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
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
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
copyFromItem and toModel aren't standard things, fill those in with your real implementation
c
Oh. Lmao
e
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
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
10 Views
Open in Slack
PreviousNext
Powered by