[PATCH] Proof of concept: thread-safe message queue
Thiago Padilha
post: https://groups.google.com/forum/#!topic/vim_dev/lylNU4Na2Nk
Heres a simple explanation of whats going on:
- A frozen 'background' thread is started at the beginning of the program.
- At every iteration, the main_loop function will wake that thread to collect
user input, and then will wait for a message
- The background thread will block until the user interacts with vim, then it
will put a message in the queue, and block until it receives another signal
from the main thread.
- When a message is put in the queue, the main_loop function unblocks,
processing
the message and continuing the loop.
The reason for going through all this message queue trouble is simple: It
enables vim to work and synchronize with multiple threads, which is a feature
missed by many vim users and plugin authors :)
For now the message queue only understands two types of messages: User input
and deferred execution of functions.
The simplest case of deferred execution is implemented by the 'defer' function,
which accepts a function name to execute on the next message loop iteration. All
this function does is put a message in the queue, and since the queue is
thread-safe, this function can be used by other threads, started by python for
example. I've written a simple python plugin which illustrates usage:
http://pastebin.com/V9VzH0zU
If youre gonna try this patch be sure to regenerate the configure script:
(cd src && make autoconf).
This is just a proof-of-concept and I have posted it only for review by
Bram and other devs. I'm sure there are better options to some of the
decisions took and I'm still very unfamiliar with the codebase.
Here are the problems I could identify and could use help fixing:
- Test 94 fails
- gVim freezes at startup. I didnt dig much into this problem but its probably
easy to fix since vim treats input from the gui in the same manner as input
from the terminal.
- I couldn't get the screen to update when running the function set by 'defer'.
In the vimscript demo you will notice that keys must be pressed to see the
updates done by the background python thread. I've tried calling
'update_screen(0)' but it just didnt work, probably theres some
check/validation to see if the user typed something before doing the actual
update.
I've done my best to modify as little as possible of the existing code. Anyone
who reads the patch will notice that while this patch introduces a new module,
not many changes were done. In fact the message_loop is implemented as a
compile-time feature, to ensure that vim will continue to work on systems
without pthreads.
I'd like to finish this post by exposing some of the benefits of refactoring
vim's design around a message-loop.
- Plugins written in extension languages(python, ruby, perl...) could make
use of threading for long running tasks and call vim back when done.
- Introduce async versions of the builtin functions that can block the UI.
For example, we could easily create the 'globAsync' and 'systemAsync'
functions that would both accept a function name as last argument. These
'async' versions of the builtin functions would do their work in non-ui
threads, which would periodically post messages with partially calculated
data to be passed to the callbacks.
Two widely used plugins could greatly benefit from this: Syntastic and CtrlP
could collect compiler output and globbed filenames in a very efficient
manner.
- Better code organization. All kinds of events(signals, mouse or keyboard)
could be modeled as specialized messages in the loop
- Bring another level of extensibility to vim:
- Terminal emulators in buffers
- IDE-like capabilities
- Write whole applications on top of vim
Some may look down upon having these features in a text editor, but notice
that these are provided by plugins, and wont affect the size or speed of
a vim default installation.
Vim may not provide an operating system but it certainly can provide a tiny
framework to build one!
- Bigger community. If vim can do more then it will attract more developers.
Thats it for now, anyone is welcome to work on this patch, just comment, send
patches or raise issues at: https://github.com/tarruda/vim/tree/event-loop
---
Filelist | 2 +
runtime/doc/eval.txt | 3 +
runtime/doc/various.txt | 1 +
src/Makefile | 5 ++
src/config.h.in | 3 +
src/configure.in | 17 +++-
src/eval.c | 25 ++++++
src/getchar.c | 8 +-
src/globals.h | 5 ++
src/main.c | 51 +++++++++++
src/message_queue.c | 226 +++++++++++++++++++++++++++++++++++++++++++++++
src/message_queue.h | 34 +++++++
src/version.c | 5 ++
src/vim.h | 4 +
14 files changed, 384 insertions(+), 5 deletions(-)
create mode 100644 src/message_queue.c
create mode 100644 src/message_queue.h
Thiago Arruda
me the impression that the lack of multithreading/message queue/event loop was a
problem to be solved in vim, and I this patch has a potential solution that has
little impact on the current code.
Any chance a dev(Bram, Ben Fritz, ZyX..) could comment? Heres the feedback I was
hoping for:
- Was I not clear about something?
- Are my assumptions valid? If not, what did I miss?
- Theres any chance I could get help? As stated in the main post, I had a few
troubles which I believe could be easily solved with the help of a developer
with more experience in hacking the code
- Is there any hope something like this will ever be merged? This is the most
important feedback because it will give me a clue on whether I should continue
to work on the patch.
Amadeus Demarzi
Benjamin Klein
> Obviously I am not a developer on this project, but as a lurker/avid vim user, I can definitely say I would love to see something like this get incorporated into the mainline vim.
--
b
Sent from my iPhone
Christian Brabandt
Wow, nice work. There are some issues, I noticed. It doesn't quite work
flawlessly
Here are some things I noticed:
- Vim didn't link with -lphtread. I fixed it for now, by declaring
LEAK_LIBS=-lpthread in the Makefile
- the output of your python plugin will be appened to whatever buffer is
currently visible. This is most probably not a problem of your patch,
but rather of your test plugin and is certainly not expected.
- I saw some random SIGSEGV (I can't seem to reproduce them so won't be
able to post a stacktrace)
- I think the redrawing issue can be solved by calling
:redraw_later(CLEAR) in the message_push() function
- sometimes, Vim doesn't seem to react anymore (probaby because it is
busy writing the data from the background thread to the main thread)
(in face, after having your plugin run for several times, Vim doesn't
seem to react anymore to :qa! and I need to kill it) As I play around
more and more, this is really critical. Vim doesn't seem to react
anymore.
(I haven't checked the gui yet).
Best,
Christian
--
Auch nach der Schulzeit gibt es kein Entrinnen vor den Bibelwerfern.
-- Frank Welker
Thiago Padilha
About this issue of vim not responding, did you try to call the Stop()
function of the test plugin? I added this function because python will
never exit by itself unless the background thread is killed.
I'm gonna try the redraw_later tip later, thanks.
Thiago
> --
> You received this message from the "vim_dev" maillist.
> Do not top-post! Type your reply below the text you are replying to.
> For more information, visit http://www.vim.org/maillist.php
>
> ---
> You received this message because you are subscribed to the Google Groups "vim_dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to vim_dev+u...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
Christian Brabandt
On So, 08 Dez 2013, Thiago Padilha wrote:
> About this issue of vim not responding, did you try to call the Stop()
> function of the test plugin? I added this function because python will
> never exit by itself unless the background thread is killed.
anymore. By attaching gdb to the process I saw, that Vim was hanging in
the python_end() function, so I think, you are right, python will never
exit unless the background thread is killed.
I tried adding some pthread_exit function calls to the getout()
function, but this did not kill the python threads. I guess, this one
needs to be taken care of, so one does not leave a hanging Vim around.
Best,
Christian
--
Christian Brabandt
fixed.
Best,
Christian
--
Der Ha� ist die Liebe, die gescheitert ist.
-- S�ren Kierkegaard
Nikolay Pavlov
It maybe needs, but it is not a problem introduced by this patch: I used to deal with hangs due to powerline threads long before this patch and the best solutions we came up with are:
1. Use daemon threads. This means thread can be interrupted at exit in virtually any state which may be a problem in some use cases.
2. As our threads were mostly waiting we used an threading.Event instance to wait and not time.sleep. I.e. thread is either wakened by triggered event in which case it exits or it is wakened after specified timeout in which case it does its job.
There are no standard ways to forcefully interrupt threads in Python so any program (plugin in our case) willing to use threads must write its own shutdown handlers. If I am not mistaking it is some design decision made on purpose.
> Best,
> Christian
> --
Thiago Padilha
>>
>> No, and by the time I noticed, it was too late, Vim wouldn't respond
>> anymore. By attaching gdb to the process I saw, that Vim was hanging in
>> the python_end() function, so I think, you are right, python will never
>> exit unless the background thread is killed.
>>
>> I tried adding some pthread_exit function calls to the getout()
>> function, but this did not kill the python threads. I guess, this one
>> needs to be taken care of, so one does not leave a hanging Vim around.
>
> BTW: There are several warnings, when compiling. They should also be
> fixed.
>
> Best,
> Christian
> --
> -- Søren Kierkegaard
Christian,
Again I thank you for the feedback, but I have no intention to continue to
working on this, simply because:
- I've read people saying that many patches will sit forever on the mailing
list without being merged.
- Until now this patch was completely ignored by vim devs, and Bram is the only
is the only person that can merge anything into mainline vim(As far as I know,
correct me if I'm wrong).
- The patch is not complete, and vim's source code is too complicated(I've seen
a few functions with 2k lines of code). It will take a considerable amount of
time for me to fully understand everything and fix the patch by myself.
- I don't have time to spend working on something that may lead to nowhere.
With that said, anyone is free to fork and improve it:
https://github.com/tarruda/vim/tree/event-loop
I will give support to anyone willing to risk it.
Thiago.
Christian Brabandt
> Again I thank you for the feedback, but I have no intention to
> continue to working on this, simply because:
>
> - I've read people saying that many patches will sit forever on the
> mailing list without being merged.
>
> - Until now this patch was completely ignored by vim devs, and Bram is
> the only is the only person that can merge anything into mainline
> vim(As far as I know, correct me if I'm wrong).
>
> - The patch is not complete, and vim's source code is too
> complicated(I've seen a few functions with 2k lines of code). It will
> take a considerable amount of time for me to fully understand
> everything and fix the patch by myself.
>
> - I don't have time to spend working on something that may lead to
> nowhere.
My hope is, that - since this is the second patch posted here within a
year or so that addresses this problem, the other being the timers patch
- it raises enough awareness to have it eventually included. I
especially liked your approach, since it used a clean and simple
approach and didn't change much besides adding the messagequeue files.
Hopefully this raises enough awareness, that Bram will finally merge it
into mainline Vim with the next minor or major release (whenever that
will be).
Best,
Christian
--
Christian Brabandt
enough.
Best,
Christian
--
Der Aberglaube macht die Gottheit zum G�tzen, und der
G�tzendiener ist um so gef�hrlicher, weil er ein Schw�rmer ist.
-- Johann Gottfried Herder (Palmb�tter)
Thiago Padilha
I have made a few modifications to the original:
- Rebased against the current master
- Removed the 'defer' function, and added an equivalent to the 'vim'
module in python's bindings. This was needed because I had no way of
knowing if vim global state was being modified by the call to 'defer'
- Use 'shell_resized' function to update the screen from background.
Not sure if this is the right way to do it but it seems to gets the
job done
- Fix the startup hang in GUI
- Include an adaptation of the 'snake' game as a demonstration of how
a multi-threaded plugin can be implemented. After compilation just
execute './src/vim -u snake.vim' to play
This still leaves test 94 failing and some random crashes in the
GUI(probably due to threading issues when reading input from Xlib).
Whenever I get free time I will work on this patch and will do my best
to keep it in sync with upstream changes.
To test just apply it or clone my github branch, be sure to call (cd
src && make autoconf) to regenerate the configure script and
enable-pythoninterp.
Hopefully, one day this will get merged.
Christian Wellenbrock
I really like this approach and hope Bram will consider this some day. Just wanted to say: Keep up the good work!
Thiago Padilha
<christian....@gmail.com> wrote:
> I really like this approach and hope Bram will consider this some day. Just wanted to say: Keep up the good work!
starting point of a personal vim fork.
Thiago Padilha
gui_start function. With this the only problem I can detect is test94
failing, I think it has something to do with operator-pending mode but
it needs to be confirmed.
I also added instructions to the github
page(https://github.com/tarruda/vim), so if anyone wants to try the
fork be sure follow those instructions as the patches posted here are
outdated.
kans
I am not hopeful for this patch, but I would love to see you succeed. We spent around two months working on adding async support to Vim without threads, https://groups.google.com/d/msg/vim_dev/-4pqDJfHCsM/LkYNCpZjQ70J . We added a timer function and called the callbacks in the main loop when appropriate. Ultimately, we gave up for a few reasons:
1. A large percent of the Vim community was outright hostile to the idea.
2. Bram was disinterested
3. Vim was unstable with the patch (segfaults outside of the patched code) AND
4. The Vim code base is abysmal.
How stable is this patch and what do you think about cross platform support?
-Matt
Ben Fritz
> Ultimately, we gave up for a few reasons:
>
> 1. A large percent of the Vim community was outright hostile to the idea.
I don't remember that at all! I think a lot of people liked the idea in general, but didn't like the idea of an uninterruptable task that would potentially take over Vim every 100 milliseconds or something. I think you were well on the way to fixing that.
There was pretty universal dislike for the idea of any "official" runtime plugin using the timed events, I think. People like their "out of the box" Vim to be very predictable.
> 2. Bram was disinterested
If I recall, Bram wanted to see tests. And the crashes fixed.
> 3. Vim was unstable with the patch (segfaults outside of the patched code) AND
> 4. The Vim code base is abysmal.
>
Yeah that's a problem, and the complexity of the patch made it hard to solve. So for this sort of thing, simpler is probably better, even if not as fully featured.
Thiago Padilha
Its very stable for me, the only problem I could detect was test94
failure. I dont think cross-platform is an issue as the only
dependency this patch introduces is pthreads, which is available in
windows through the pthreads-win32 library.
I'm not raising my hopes too high, but in any case I think this patch
can be used as a base for a modern vim fork so I will keep maintaining
it.
About your patch, I was sorry it didnt get accepted. Even so I
encourage you to join me as the timer functions proposed in your patch
can easily be implemented on top of a message queue. I have enabled
the issue tracker at https://github.com/tarruda/vim to document
pending issues and extend discussions.
kans
Thiago,
It would be rather trivial for us to push timeout events into the queue as you suggested- our code already does this, but from a slightly different place than you hooked. I believe the last bug that stopped us was in memfile.c (which hasn't been touched in a decade) with a memory corruption error. In our experience, Vim is only robust in so much as you don't step outside of the normal flow which makes me suspicious you will run into the same problems. I'm guessing that CursorHold and friends may also need work. At any rate, I'll have a look at your patch and try to get the Floobits python plugin to work on top of it.
-Matt
Ashley Hewson
I would love this to work and I thank you for your effort, but I'm quite doubtful that vgetc can be safely run in a background thread. It simply does too much work. Just to pick one example, it appears to be responsible for blinking the GUI cursor while it's waiting, which will obviously conflict with any screen updates the main thread is doing. I've built your fork with TSan[1] enabled and run snake.vim and it complains of many other race conditions. I can send you the log if you're interested but I would suggest using TSan yourself.
Best,
Ash
[1] TSan: http://code.google.com/p/thread-sanitizer
Ben Fritz
> Thiago,
>
> I would love this to work and I thank you for your effort, but I'm quite doubtful that vgetc can be safely run in a background thread. It simply does too much work. Just to pick one example, it appears to be responsible for blinking the GUI cursor while it's waiting, which will obviously conflict with any screen updates the main thread is doing.
I thought the idea of this patch, was to allow background threads to send Vim a message, that says "when you get a chance, run function X". Then, at some later point in time, when Vim is not busy, it will run function X *IN THE MAIN THREAD*. Thus there should be no conflict between the deferred function and the main thread. Am I correct in this?
If so, plugin authors must simply ensure that function X is threadsafe with the background functions in the same thread. This probably means making sure that the background thread is DONE with whatever data function X will access, until function X can run and is done with that data.
Thiago Padilha
>
> I thought the idea of this patch, was to allow background threads to send Vim a message, that says "when you get a chance, run function X". Then, at some later point in time, when Vim is not busy, it will run function X *IN THE MAIN THREAD*. Thus there should be no conflict between the deferred function and the main thread. Am I correct in this?
>
> If so, plugin authors must simply ensure that function X is threadsafe with the background functions in the same thread. This probably means making sure that the background thread is DONE with whatever data function X will access, until function X can run and is done with that data.
asynchronous messages from other threads. Thats why plugin authors need to use
cursorhold polls to receive updates from other threads or processes.
This patch makes a relatively small change to the main_loop function so it will
block waiting for arbitrary messages from the queue, where messages can be user
input or deferred calls(Though it can easily be extended to handle other types
of asynchronous events such as signals).
Look at this section of the code:
https://github.com/tarruda/vim/blob/event-loop/src/main.c#L1337-L1384
As you can see, the background thread will not call vgetc until its notified by
the main thread(the 'input_notify()' call). So even if the main thread is doing
something at the time user is typing, the background thread will still be
frozen waiting for a signal from the main thread. That means its not possible
for that two 'vgetc' calls happen at the time time.
To illustrate, consider that at a certain point the main thread is waiting for
messages, and the background thread is waiting for input. Now suppose that the
following sequence of events happen:
- Two chars are entered in a *very* fast sequence. For the sake of
argument imagine
they were entered at the same time but one after another
- The background thread will read a single char with vgetc and the OS
buffer will
be left with one char.
- The background thread will send an 'UserInput' message to the main thread and
then will go back to sleep(not to vgetc)
- The main thread will put the received char into special variables that will be
inspected by vgetc before trying to read input(and so wont block the main
thread)
- The main thread will invoke normal_cmd as usual(which will itself invoke
vgetc), eventually fall back into input_notify() and then block for more
messages.
- The background thread will wake, call vgetc, read the pending char from the OS
buffer and then the process repeats.
> On Wednesday, January 15, 2014 4:44:34 AM UTC-6, Ashley Hewson wrote:
>> Thiago,
>>
>> I would love this to work and I thank you for your effort, but I'm quite doubtful that vgetc can be safely run in a background thread. It simply does too much work. Just to pick one example, it appears to be responsible for blinking the GUI cursor while it's waiting, which will obviously conflict with any screen updates the main thread is doing.
the background thread is in the middle of running 'vgetc'. A DeferredCall will
invoke a vimscript function and then will update the screen which might cause
the race condition. Thanks for pointing that bug, I could not see it at first.
That might be the reason I had to call XInitThreads in the GUI
version. One possible fix is
to synchronize the call to 'shell_rezise' (which does the screen
update) with the
call to vgetc from the background thread. When I get the time I will see if that
works(If you test it sooner please send me updates).
Its perfectly possible that we cant make vim thread safe without refactoring
vgetc or other parts of the code. As the title says, the patch was more a
proof-of-concept, and my main goal(other than making it thread-safe) was to
build interest from the community and touch as little as possible of existing
code(see the vungetc hack on the snippet I linked). In any case, I'm glad
that you joined me in this "battle" :)
Best regard
Thiago
Ben Fritz
>
>
> Ashley, its possible that a 'DeferredCall' message arrives while
>
> the background thread is in the middle of running 'vgetc'. A DeferredCall will
>
> invoke a vimscript function and then will update the screen which might cause
>
> the race condition. Thanks for pointing that bug, I could not see it at first.
>
So, your background thread is directly calling a function to get user input/update the screen? I think THAT is a mistake. This should not happen. A background thread can be used for data processing, but any user input, buffer changes, screen updates, etc. should ALWAYS be handled in the main thread, possibly in a deferred function. A background thread should ALWAYS be able to have the main thread interrupt it. Calling functions in the background which remove things from Vim's input queue or redraw the screen is begging for trouble. I thought that was the point of the deferred functions, to allow all such things to happen in the foreground thread. If you allow calling any arbitrary Vim function in a background thread, then we would need to make every arbitrary Vim function thread-safe, and this project becomes huge to the point of being unmanageable.
I think the "deferred function executed in the main thread" is a clever idea, but to use it the background thread can only access data that the foreground thread will not be accessing, except in the deferred function designed for it. Redrawing the screen, getting user input, or whatever all need to happen in the foreground thread ONLY. If you need to change text or redraw the screen, call a deferred function to do it.
Thiago Padilha
> So, your background thread is directly calling a function to get user input/update the screen? I think THAT is a mistake. This should not happen. A background thread can be used for data processing, but any user input, buffer changes, screen updates, etc. should ALWAYS be handled in the main thread, possibly in a deferred function. A background thread should ALWAYS be able to have the main thread interrupt it. Calling functions in the background which remove things from Vim's input queue or redraw the screen is begging for trouble. I thought that was the point of the deferred functions, to allow all such things to happen in the foreground thread. If you allow calling any arbitrary Vim function in a background thread, then we would need to make every arbitrary Vim function thread-safe, and this project becomes huge to the point of being unmanageable.
>
> I think the "deferred function executed in the main thread" is a clever idea, but to use it the background thread can only access data that the foreground thread will not be accessing, except in the deferred function designed for it. Redrawing the screen, getting user input, or whatever all need to happen in the foreground thread ONLY. If you need to change text or redraw the screen, call a deferred function to do it.
>
main thread. That is required because the main thread will block waiting for a
message, which can come from other threads. The only way I know of making a
single-threaded program wait for multiple events is through select-like system
calls, but then the 'messages' would have to come from other processes
Juan Campa
> I thought the idea of this patch, was to allow background threads to send Vim a message, that says "when you get a chance, run function X". Then, at some later point in time, when Vim is not busy, it will run function X *IN THE MAIN THREAD*. Thus there should be no conflict between the deferred function and the main thread. Am I correct in this?
>
> If so, plugin authors must simply ensure that function X is threadsafe with the background functions in the same thread. This probably means making sure that the background thread is DONE with whatever data function X will access, until function X can run and is done with that data.
Hey guys, I hope I'm not late for this conversation.
I've implemented a method to call deferred functions in the main thread from a another thread (I'm using python's threading library for that). It works by spawning another instance of vim from the thread to send a command to the current instance (i.e. vim --servername <this instance's servername> --remote-expr <function to call>) so main thread ends up calling the specified function when it gets the chance.
Now, before you burn me alive, I now there's a lot of unnecessary overhead in this method ("spawning another Vim? Are you insane!?") but it's working surprisingly well for the use cases I have, i.e. it's all transparent for the user and I can't notice any performance hits.
My point is that I suspect (with high levels of confidence) that this same mechanism could be leveraged but without having to spawn a separate vim instance. This would require minimal source changes and it should just work because it would use the same mechanisms that are already working rock solid.
Let me know what do you think.
ZyX
> On Wednesday, January 15, 2014 9:44:24 AM UTC-5, Ben Fritz wrote:
> > I thought the idea of this patch, was to allow background threads to send Vim a message, that says "when you get a chance, run function X". Then, at some later point in time, when Vim is not busy, it will run function X *IN THE MAIN THREAD*. Thus there should be no conflict between the deferred function and the main thread. Am I correct in this?
> >
> > If so, plugin authors must simply ensure that function X is threadsafe with the background functions in the same thread. This probably means making sure that the background thread is DONE with whatever data function X will access, until function X can run and is done with that data.
>
> Hey guys, I hope I'm not late for this conversation.
>
> I've implemented a method to call deferred functions in the main thread from a another thread (I'm using python's threading library for that). It works by spawning another instance of vim from the thread to send a command to the current instance (i.e. vim --servername <this instance's servername> --remote-expr <function to call>) so main thread ends up calling the specified function when it gets the chance.
Not when it gets the chance. Check out the following: make server run `while 1 | sleep 1 | endwhile` and send that expression (I tested it on `input("abc")`). You will see that despite something being run received expression will still be processed. Though I am unable to reproduce this I remember @MarcWeber complaining about random crashes when using this feature on daily basis. Not too likely but still happening.
Juan Campa
> Not when it gets the chance. Check out the following: make server run `while 1 | sleep 1 | endwhile` and send that expression (I tested it on `input("abc")`). You will see that despite something being run received expression will still be processed. Though I am unable to reproduce this I remember @MarcWeber complaining about random crashes when using this feature on daily basis. Not too likely but still happening.
That was unexpected. I'll take a look into Vim's code just out of curiosity to see how these remote calls are being handled. I guess I have to wait for a robust solution to this problem but in the meantime I'll work with this solution and hope the odds favor me.
Thanks for pointing that out ZyX, please let me know if you find a way to make this work.