fare
commented
9 years ago Just to make sure: are you using the data structure concurrently, or is there only one thread at a time accessing the data structure?
Open lokedhs opened 9 years ago
fare
commented
9 years ago Just to make sure: are you using the data structure concurrently, or is there only one thread at a time accessing the data structure?
gwkkwg
commented
9 years ago Hi Elias,
Unfortunately, I’m not really maintaining CL-Containers anymore :-(.
As Faré asked, is this with concurrent access or single threaded? If the former, I’m not surprised as CL-Containers was not developed to be MP safe.
If you can create a smallish, reproducible test case, I will certainly take a look.
regards,
On Aug 20, 2015, at 12:54 AM, Elias Mårtenson notifications@github.com wrote:
I get this problem sometimes when I perform a very large number of insertions and deletions. I haven't been able to reproduce this using a small test case, although I get it all the time when putting high load on the system
This is the error I'm getting:
There is no applicable method for the generic function
<STANDARD-GENERIC-FUNCTION METABANG.CL-CONTAINERS::RBT-COLOR (1)>
when called with arguments (NIL). Here's the full stack trace:
0: ((LAMBDA NIL :IN SB-DEBUG::FUNCALL-WITH-DEBUG-IO-SYNTAX)) 1: (SB-IMPL::CALL-WITH-SANE-IO-SYNTAX #<CLOSURE (LAMBDA NIL :IN SB-DEBUG::FUNCALL-WITH-DEBUG-IO-SYNTAX) {100A62EA1B}>) 2: (SB-IMPL::%WITH-STANDARD-IO-SYNTAX #<CLOSURE (LAMBDA NIL :IN SB-DEBUG::FUNCALL-WITH-DEBUG-IO-SYNTAX) {100A62E9EB}>) 3: (PRINT-BACKTRACE :STREAM #<SB-IMPL::STRING-OUTPUT-STREAM {100A62E923}> :START 0 :FROM :DEBUGGER-FRAME :COUNT 4611686018427387903 :PRINT-THREAD T :PRINT-FRAME-SOURCE NIL :METHOD-FRAME-STYLE NIL) 4: (TRIVIAL-BACKTRACE:PRINT-BACKTRACE-TO-STREAM #<SB-IMPL::STRING-OUTPUT-STREAM {100A62E923}>) 5: ((FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP) #<SB-PRETTY:PRETTY-STREAM {100A62E633}>) 6: ((LAMBDA (STREAM LOG4CL-IMPL::FMT-INFO LOG4CL-IMPL::LOGGER LOG4CL-IMPL::LOG-LEVEL LOG4CL-IMPL::LOG-FUNC) :IN \"/home/emartenson/quicklisp/dists/quicklisp/software/log4cl-20141217-git/src/pattern-layout.lisp\") #<SB-PRETTY:PRETTY-STREAM {100A62E633}> #<LOG4CL-IMPL::FORMAT-INFO {100EB9D603}> #
# #<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP) {100B430BCB}>) 7: ((LAMBDA (STREAM LOG4CL-IMPL::LOGGER LOG4CL-IMPL::LEVEL LOG4CL-IMPL::LOG-FUNC) :IN LOG4CL-IMPL::COMPILE-PATTERN-FORMAT) #<SB-PRETTY:PRETTY-STREAM {100A62E633}> #<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON.TIMER.TIMER-THREAD-LOOP /home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}> 4 #<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP) {100B430BCB}>) 8: ((FLET #:WITH-PRETTY-STREAM3039 :IN SB-PRETTY::CALL-LOGICAL-BLOCK-PRINTER) #<SB-PRETTY:PRETTY-STREAM {100A62E633}>) 9: (SB-PRETTY::CALL-LOGICAL-BLOCK-PRINTER #<CLOSURE (FLET #:PPRINT-BLOCK :IN \"/home/emartenson/quicklisp/dists/quicklisp/software/log4cl-20141217-git/src/pattern-layout.lisp\") {7FFFC89E57AB}> #<SWANK/GRAY::SLIME-OUTPUT-STREAM {1003C46553}> NIL NIL \"\" NIL) 10: ((LAMBDA (STREAM LOG4CL-IMPL::FMT-INFO LOG4CL-IMPL::LOGGER LOG4CL-IMPL::LOG-LEVEL LOG4CL-IMPL::LOG-FUNC LOG4CL-IMPL::WRAP) :IN \"/home/emartenson/quicklisp/dists/quicklisp/software/log4cl-20141217-git/src/pattern-layout.lisp\") #<SWANK/GRAY::SLIME-OUTPUT-STREAM {1003C46553}> #<LOG4CL-IMPL::PATTERN-PRETTY-FMT-INFO {1009C06EE3}> #<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON.TIMER.TIMER-THREAD-LOOP /home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}> 4 #<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP) {100B430BCB}> #<CLOSURE (LAMBDA (STREAM LOG4CL-IMPL::LOGGER LOG4CL-IMPL::LEVEL LOG4CL-IMPL::LOG-FUNC) :IN LOG4CL-IMPL::COMPILE-PATTERN-FORMAT) {100DE5CF8B}>) 11: ((LAMBDA (STREAM LOG4CL-IMPL::LOGGER LOG4CL-IMPL::LEVEL LOG4CL-IMPL::LOG-FUNC) :IN LOG4CL-IMPL::COMPILE-PATTERN-FORMAT) #<SWANK/GRAY::SLIME-OUTPUT-STREAM {1003C46553}> #<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON.TIMER.TIMER-THREAD-LOOP /home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}> 4 #<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP) {100B430BCB}>) 12: ((:METHOD LOG4CL-IMPL:LAYOUT-TO-STREAM (LOG4CL-IMPL:PATTERN-LAYOUT T T T T)) #<LOG4CL-IMPL:PATTERN-LAYOUT {10037D2463}> #<SWANK/GRAY::SLIME-OUTPUT-STREAM {1003C46553}> #<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON.TIMER.TIMER-THREAD-LOOP /home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}> 4 #<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP) {100B430BCB}>) [fast-method] 13: ((:METHOD LOG4CL-IMPL:APPENDER-DO-APPEND (LOG4CL-IMPL::FIXED-STREAM-APPENDER-BASE T T T)) #<LOG4CL-IMPL:TRICKY-CONSOLE-APPENDER {100807D803}> #<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON.TIMER.TIMER-THREAD-LOOP /home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}> 4 #<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP) {100B430BCB}>) [fast-method] 14: ((FLET #:WITHOUT-INTERRUPTS-BODY-543 :IN SB-THREAD::CALL-WITH-MUTEX)) 15: (SB-THREAD::CALL-WITH-MUTEX #<CLOSURE (FLET SB-THREAD::WITH-MUTEX-THUNK :IN LOG4CL-IMPL:APPENDER-DO-APPEND) {7FFFC89E5BBB}> #<SB-THREAD:MUTEX \"Anonymous lock\" owner: #<SB-THREAD:THREAD \"Timer manager thread: RabbitMQ Notifications timer queue\" RUNNING {1007C836A3}>> NIL T NIL) 16: ((:METHOD LOG4CL-IMPL:APPENDER-DO-APPEND :AROUND (LOG4CL-IMPL:SERIALIZED-APPENDER T T T)) #<LOG4CL-IMPL:TRICKY-CONSOLE-APPENDER {100807D803}> #<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON.TIMER.TIMER-THREAD-LOOP /home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}> 4 #<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP) {100B430BCB}>) [fast-method] 17: ((LABELS LOG4CL-IMPL::LOG-TO-LOGGER-APPENDERS :IN LOG4CL-IMPL::LOG-WITH-LOGGER) #<LOGGER +ROOT+ {10037299E3}> #<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON.TIMER.TIMER-THREAD-LOOP /home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}> 4 #<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP) {100B430BCB}>) 18: ((LABELS LOG4CL-IMPL::LOG-TO-LOGGER-APPENDERS :IN LOG4CL-IMPL::LOG-WITH-LOGGER) #<LOG4CL-IMPL::FILE-LOGGER POTATO NIL {100350FC23}> #<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON.TIMER.TIMER-THREAD-LOOP /home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}> 4 #<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP) {100B430BCB}>) 19: ((LABELS LOG4CL-IMPL::LOG-TO-LOGGER-APPENDERS :IN LOG4CL-IMPL::LOG-WITH-LOGGER) #<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON NIL {100485F943}> #<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON.TIMER.TIMER-THREAD-LOOP /home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}> 4 #<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP) {100B430BCB}>) 20: ((LABELS LOG4CL-IMPL::LOG-TO-LOGGER-APPENDERS :IN LOG4CL-IMPL::LOG-WITH-LOGGER) #<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON.TIMER NIL {10037A2C53}> #<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON.TIMER.TIMER-THREAD-LOOP /home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}> 4 #<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP) {100B430BCB}>) 21: ((LABELS LOG4CL-IMPL::LOG-TO-LOGGER-APPENDERS :IN LOG4CL-IMPL::LOG-WITH-LOGGER) #<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON.TIMER.TIMER-THREAD-LOOP /home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}> #<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON.TIMER.TIMER-THREAD-LOOP /home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}> 4 #<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP) {100B430BCB}>) 22: (LOG4CL-IMPL::LOG-WITH-LOGGER #<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON.TIMER.TIMER-THREAD-LOOP /home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}> 4 #<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP) {100B430BCB}> #<PACKAGE \"POTATO.COMMON.TIMER\">) 23: ((FLET #:H0 :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP) # ) 24: (SIGNAL #<SIMPLE-ERROR \"~@<There is no applicable method for the generic function ~2I~_~S~ ~I~when called with arguments ~2I~~S.~:>\" {10074CFDC3}>) 25: (ERROR \"~@<There is no applicable method for the generic function ~2I~_~S~ ~I~when called with arguments ~2I~~S.~:>\" #<STANDARD-GENERIC-FUNCTION METABANG.CL-CONTAINERS::RBT-COLOR (1)> (NIL)) 26: ((:METHOD NO-APPLICABLE-METHOD (T)) #<STANDARD-GENERIC-FUNCTION METABANG.CL-CONTAINERS::RBT-COLOR (1)> NIL) [fast-method] 27: ((LAMBDA (SB-PCL::.ARG0. SB-INT:&MORE SB-PCL::.DFUN-MORE-CONTEXT. SB-PCL::.DFUN-MORE-COUNT.) :IN \"/home/emartenson/.cache/common-lisp/sbcl-1.2.14.58-ad79278-linux-x64/home/emartenson/prog/potato/src/potato/metaclasses.fasl\") #<STANDARD-GENERIC-FUNCTION METABANG.CL-CONTAINERS::RBT-COLOR (1)> NIL) — Reply to this email directly or view it on GitHub https://github.com/gwkkwg/cl-containers/issues/6.
Gary Warren King, metabang.com http://metabang.com/ Cell: (413) 559 8738 Fax: (206) 338-4052 gwkkwg on Skype * garethsan on AIM * gwking on twitter
lokedhs
commented
9 years ago This is single threaded access. I will try to write some debug code that records every access to the tree so that I can create a list that reproduces the problem.
Regards, Elias On 23 Aug 2015 02:38, "gwkkwg" notifications@github.com wrote:
Hi Elias,
Unfortunately, I’m not really maintaining CL-Containers anymore :-(.
As Faré asked, is this with concurrent access or single threaded? If the former, I’m not surprised as CL-Containers was not developed to be MP safe.
If you can create a smallish, reproducible test case, I will certainly take a look.
regards,
On Aug 20, 2015, at 12:54 AM, Elias Mårtenson notifications@github.com wrote:
I get this problem sometimes when I perform a very large number of insertions and deletions. I haven't been able to reproduce this using a small test case, although I get it all the time when putting high load on the system
This is the error I'm getting:
There is no applicable method for the generic function
<STANDARD-GENERIC-FUNCTION METABANG.CL-CONTAINERS::RBT-COLOR (1)>
when called with arguments (NIL). Here's the full stack trace:
0: ((LAMBDA NIL :IN SB-DEBUG::FUNCALL-WITH-DEBUG-IO-SYNTAX)) 1: (SB-IMPL::CALL-WITH-SANE-IO-SYNTAX #<CLOSURE (LAMBDA NIL :IN SB-DEBUG::FUNCALL-WITH-DEBUG-IO-SYNTAX) {100A62EA1B}>) 2: (SB-IMPL::%WITH-STANDARD-IO-SYNTAX #<CLOSURE (LAMBDA NIL :IN SB-DEBUG::FUNCALL-WITH-DEBUG-IO-SYNTAX) {100A62E9EB}>) 3: (PRINT-BACKTRACE :STREAM #<SB-IMPL::STRING-OUTPUT-STREAM {100A62E923}> :START 0 :FROM :DEBUGGER-FRAME :COUNT 4611686018427387903 :PRINT-THREAD T :PRINT-FRAME-SOURCE NIL :METHOD-FRAME-STYLE NIL) 4: (TRIVIAL-BACKTRACE:PRINT-BACKTRACE-TO-STREAM
<SB-IMPL::STRING-OUTPUT-STREAM {100A62E923}>)
5: ((FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP)
<SB-PRETTY:PRETTY-STREAM {100A62E633}>)
6: ((LAMBDA (STREAM LOG4CL-IMPL::FMT-INFO LOG4CL-IMPL::LOGGER LOG4CL-IMPL::LOG-LEVEL LOG4CL-IMPL::LOG-FUNC) :IN \"/home/emartenson/quicklisp/dists/quicklisp/software/log4cl-20141217-git/src/pattern-layout.lisp\")
<SB-PRETTY:PRETTY-STREAM {100A62E633}> #<LOG4CL-IMPL::FORMAT-INFO
{100EB9D603}> #
# #<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP) {100B430BCB}>) 7: ((LAMBDA (STREAM LOG4CL-IMPL::LOGGER LOG4CL-IMPL::LEVEL LOG4CL-IMPL::LOG-FUNC) :IN LOG4CL-IMPL::COMPILE-PATTERN-FORMAT) <SB-PRETTY:PRETTY-STREAM {100A62E633}> #<LOG4CL-IMPL::FILE-LOGGER
POTATO.COMMON.TIMER.TIMER-THREAD-LOOP /home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}> 4
<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP)
{100B430BCB}>) 8: ((FLET #:WITH-PRETTY-STREAM3039 :IN SB-PRETTY::CALL-LOGICAL-BLOCK-PRINTER) #<SB-PRETTY:PRETTY-STREAM {100A62E633}>) 9: (SB-PRETTY::CALL-LOGICAL-BLOCK-PRINTER #<CLOSURE (FLET #:PPRINT-BLOCK :IN \"/home/emartenson/quicklisp/dists/quicklisp/software/log4cl-20141217-git/src/pattern-layout.lisp\") {7FFFC89E57AB}> #<SWANK/GRAY::SLIME-OUTPUT-STREAM {1003C46553}> NIL NIL \"\" NIL) 10: ((LAMBDA (STREAM LOG4CL-IMPL::FMT-INFO LOG4CL-IMPL::LOGGER LOG4CL-IMPL::LOG-LEVEL LOG4CL-IMPL::LOG-FUNC LOG4CL-IMPL::WRAP) :IN \"/home/emartenson/quicklisp/dists/quicklisp/software/log4cl-20141217-git/src/pattern-layout.lisp\")
<SWANK/GRAY::SLIME-OUTPUT-STREAM {1003C46553}>
<LOG4CL-IMPL::PATTERN-PRETTY-FMT-INFO {1009C06EE3}>
<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON.TIMER.TIMER-THREAD-LOOP
/home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}> 4
<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP)
{100B430BCB}> #<CLOSURE (LAMBDA (STREAM LOG4CL-IMPL::LOGGER LOG4CL-IMPL::LEVEL LOG4CL-IMPL::LOG-FUNC) :IN LOG4CL-IMPL::COMPILE-PATTERN-FORMAT) {100DE5CF8B}>) 11: ((LAMBDA (STREAM LOG4CL-IMPL::LOGGER LOG4CL-IMPL::LEVEL LOG4CL-IMPL::LOG-FUNC) :IN LOG4CL-IMPL::COMPILE-PATTERN-FORMAT)
<SWANK/GRAY::SLIME-OUTPUT-STREAM {1003C46553}> #<LOG4CL-IMPL::FILE-LOGGER
POTATO.COMMON.TIMER.TIMER-THREAD-LOOP /home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}> 4
<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP)
{100B430BCB}>) 12: ((:METHOD LOG4CL-IMPL:LAYOUT-TO-STREAM (LOG4CL-IMPL:PATTERN-LAYOUT T T T T)) #<LOG4CL-IMPL:PATTERN-LAYOUT {10037D2463}>
<SWANK/GRAY::SLIME-OUTPUT-STREAM {1003C46553}> #<LOG4CL-IMPL::FILE-LOGGER
POTATO.COMMON.TIMER.TIMER-THREAD-LOOP /home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}> 4
<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP)
{100B430BCB}>) [fast-method] 13: ((:METHOD LOG4CL-IMPL:APPENDER-DO-APPEND (LOG4CL-IMPL::FIXED-STREAM-APPENDER-BASE T T T))
<LOG4CL-IMPL:TRICKY-CONSOLE-APPENDER {100807D803}>
<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON.TIMER.TIMER-THREAD-LOOP
/home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}> 4
<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP)
{100B430BCB}>) [fast-method] 14: ((FLET #:WITHOUT-INTERRUPTS-BODY-543 :IN SB-THREAD::CALL-WITH-MUTEX)) 15: (SB-THREAD::CALL-WITH-MUTEX #<CLOSURE (FLET SB-THREAD::WITH-MUTEX-THUNK :IN LOG4CL-IMPL:APPENDER-DO-APPEND) {7FFFC89E5BBB}> #<SB-THREAD:MUTEX \"Anonymous lock\" owner:
<SB-THREAD:THREAD \"Timer manager thread: RabbitMQ Notifications timer
queue\" RUNNING {1007C836A3}>> NIL T NIL) 16: ((:METHOD LOG4CL-IMPL:APPENDER-DO-APPEND :AROUND (LOG4CL-IMPL:SERIALIZED-APPENDER T T T))
<LOG4CL-IMPL:TRICKY-CONSOLE-APPENDER {100807D803}>
<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON.TIMER.TIMER-THREAD-LOOP
/home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}> 4
<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP)
{100B430BCB}>) [fast-method] 17: ((LABELS LOG4CL-IMPL::LOG-TO-LOGGER-APPENDERS :IN LOG4CL-IMPL::LOG-WITH-LOGGER) #<LOGGER +ROOT+ {10037299E3}>
<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON.TIMER.TIMER-THREAD-LOOP
/home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}> 4
<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP)
{100B430BCB}>) 18: ((LABELS LOG4CL-IMPL::LOG-TO-LOGGER-APPENDERS :IN LOG4CL-IMPL::LOG-WITH-LOGGER) #<LOG4CL-IMPL::FILE-LOGGER POTATO NIL {100350FC23}> #<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON.TIMER.TIMER-THREAD-LOOP /home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}> 4
<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP)
{100B430BCB}>) 19: ((LABELS LOG4CL-IMPL::LOG-TO-LOGGER-APPENDERS :IN LOG4CL-IMPL::LOG-WITH-LOGGER) #<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON NIL {100485F943}> #<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON.TIMER.TIMER-THREAD-LOOP /home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}> 4
<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP)
{100B430BCB}>) 20: ((LABELS LOG4CL-IMPL::LOG-TO-LOGGER-APPENDERS :IN LOG4CL-IMPL::LOG-WITH-LOGGER) #<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON.TIMER NIL {10037A2C53}> #<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON.TIMER.TIMER-THREAD-LOOP /home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}> 4
<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP)
{100B430BCB}>) 21: ((LABELS LOG4CL-IMPL::LOG-TO-LOGGER-APPENDERS :IN LOG4CL-IMPL::LOG-WITH-LOGGER) #<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON.TIMER.TIMER-THREAD-LOOP /home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}>
<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON.TIMER.TIMER-THREAD-LOOP
/home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}> 4
<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP)
{100B430BCB}>) 22: (LOG4CL-IMPL::LOG-WITH-LOGGER #<LOG4CL-IMPL::FILE-LOGGER POTATO.COMMON.TIMER.TIMER-THREAD-LOOP /home/emartenson/prog/potato/src/common/timer.lisp {100354B0A3}> 4
<FUNCTION (FLET #:|log-stmt75| :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP)
{100B430BCB}> #<PACKAGE \"POTATO.COMMON.TIMER\">) 23: ((FLET #:H0 :IN POTATO.COMMON.TIMER::TIMER-THREAD-LOOP) #<unused argument>) 24: (SIGNAL #<SIMPLE-ERROR \"~@<There is no applicable method for the generic function ~2I~_~S~ ~I~when called with arguments ~2I~~S.~:>\" {10074CFDC3}>) 25: (ERROR \"~@<There is no applicable method for the generic function ~2I~_~S~ ~I~when called with arguments ~2I~~S.~:>\" #<STANDARD-GENERIC-FUNCTION METABANG.CL-CONTAINERS::RBT-COLOR (1)> (NIL)) 26: ((:METHOD NO-APPLICABLE-METHOD (T)) #<STANDARD-GENERIC-FUNCTION METABANG.CL-CONTAINERS::RBT-COLOR (1)> NIL) [fast-method] 27: ((LAMBDA (SB-PCL::.ARG0. SB-INT:&MORE SB-PCL::.DFUN-MORE-CONTEXT. SB-PCL::.DFUN-MORE-COUNT.) :IN \"/home/emartenson/.cache/common-lisp/sbcl-1.2.14.58-ad79278-linux-x64/home/emartenson/prog/potato/src/potato/metaclasses.fasl\")
<STANDARD-GENERIC-FUNCTION METABANG.CL-CONTAINERS::RBT-COLOR (1)> NIL)
— Reply to this email directly or view it on GitHub < https://github.com/gwkkwg/cl-containers/issues/6>.
Gary Warren King, metabang.com http://metabang.com/ Cell: (413) 559 8738 Fax: (206) 338-4052 gwkkwg on Skype * garethsan on AIM * gwking on twitter
— Reply to this email directly or view it on GitHub https://github.com/gwkkwg/cl-containers/issues/6#issuecomment-133738968.
lokedhs
commented
9 years ago I have been able to reproduce the problem. It happens when two threads are inserting/deleting elements at the same time, even though the threads are independently operating on different containers.
Here is the test code: https://gist.github.com/lokedhs/197c00e4bec064a58287
The key part of the code is the following loop:
(defun test-rbt (values)
(let ((q (make-instance 'cl-containers:red-black-tree
:sorter #'element<
:test #'element=
:key #'identity)))
(loop
for (cmd value) in values
do (ecase cmd
(:insert (cl-containers:insert-item q value))
(:remove (cl-containers:delete-item q value))))
q))The container q is never accessed outside of this function, and should therefore not be affected by any other threads. I then run this function twice in two parallel threads:
(defun test-rbt-threaded ()
(loop
repeat 2
do (bordeaux-threads:make-thread (lambda () (test-rbt *test-values1*)))))This will trigger the bug.
lokedhs
commented
9 years ago The same error occurs on CCL, which suggests that this is indeed a problem with cl-containers and not with the CL implementation.
lokedhs
commented
9 years ago I created a subclass of rbt-node that raises an error if its values are changed and I set *rbt-empty-node* to be an instance of this class instead: https://gist.github.com/lokedhs/cb5da5468aedbeef6452
Once this is done, you very quickly get an error in delete-node where the parent of the empty node is changed. See the comment in the code for the function below:
(defmethod delete-node ((tree red-black-tree) (item red-black-node))
(let ((y nil) (x nil))
(if (or (eq (left-child item) *rbt-empty-node*)
(eq (right-child item) *rbt-empty-node*))
(setf y item)
(setf y (successor tree item)))
(if (eq (left-child y) *rbt-empty-node*)
(setf x (right-child y))
(setf x (left-child y)))
(setf (parent x) (parent y)) ; <-- the empty node is changed here
(if (eq (parent y) *rbt-empty-node*)
(setf (root tree) x)
(if (eq y (left-child (parent y)))
(setf (left-child (parent y)) x)
(setf (right-child (parent y)) x)))
(when (not (eq y item))
(setf (element item) (element y)))
(when (= (rbt-color y) +rbt-color-black+)
;(break)
(rb-delete-fixup tree x))
y))I have been using the subclass RBT-EMPTY-NODE to track down the places where the empty node gets modified, and there are a lot of places where this happens. I'm not understanding fully what RB-DELETE-FIXUP does, but it seems to me that it doesn't take the empty nodes into account at all. I really can't figure out how to fix this.
fare
commented
9 years ago You're already more of a cl-container maintainer than I am, I fear.
If you get it running, are you interested in commit rights?
(And if you don't — well, lisp-interface-library has avl trees.)
pinterface
commented
9 years ago This caught my interest in IRC. Feel free to ignore me or tell me off if I'm way off base:
@gwkkwg can correct me if I'm wrong, but I'm guessing *rbt-empty-node* exists precisely so most things don't need to take the empty node into account. It's clever, in a similar vein to how some CL implementations implement NIL as a cons cell whose car and cdr point to itself to avoid needing to check for nil in #'car and #'cdr. Works great until, you know, threads happen.
One workaround you could try would be:
(push (cons 'cl-containers::*rbt-empty-node*
'(make-instance 'cl-containers::red-black-node
:right-child nil
:left-child nil
:element nil))
bordeaux-threads:*default-special-bindings*)Which at least gives each thread its own empty node. Would probably fall apart under an event-driven model, though. (That you could theoretically fix by making the empty node per-tree. Though somewhere in there you may cross the threshold where it becomes worth adjusting things to check for the empty node everywhere, as you're attempting to do.)
lokedhs
commented
9 years ago This indeed seems to be the problem. I was looking at this implementation in C, here: http://web.mit.edu/~emin/Desktop/ref_to_emin/www.old/source_code/red_black_tree/index.html which seems to be related to the implementation in cl-containers, and I now have a better understanding of the implementation.
This C implementation has the following comment, which I believe actually describes the issue we are seeing here:
/* I originally wrote this function to use the sentinel for */
/* nil to avoid checking for nil. However this introduces a */
/* very subtle bug because sometimes this function modifies */
/* the parent pointer of nil. This can be a problem if a */
/* function which calls LeftRotate also uses the nil sentinel */
/* and expects the nil sentinel's parent pointer to be unchanged */
/* after calling this function. For example, when RBDeleteFixUP */
/* calls LeftRotate it expects the parent pointer of nil to be */
/* unchanged. */They solve the problem by letting the empty node be local to the tree itself, and that's probably the best solution for cl-containers too.
I get this problem sometimes when I perform a very large number of insertions and deletions. I haven't been able to reproduce this using a small test case, although I get it all the time when putting high load on the system
This is the error I'm getting:
Here's the full stack trace: