Modern data structures -
i realized data structures regularly use old , simple. linked lists, hash tables, trees, , more complex variants such vlists or rbtrees pretty old inventions.
most of them conceived serial, single cpu world , require adapting work in parallel environments.
what kind of newer, better data structures have? why not used?
i understand using plain old linked list if have implement , prefer simplicity, having huge stls , piles of third party libraries guava or boost, why still placing locks around hashes?
don't have potentially standard, hard-proven modern data structures can replace trusty old-timers?
there nothing wrong old ones. way keep flexibility separate concerns. normal (old style) datastructures concerned way how data stored. locking different concern, should not part of datastructure.
locking potentially expensive operation, if can, should lock multiple structures @ once optimize code. i.e. lock critical sections not datastructures. if directly add locking datastructures, not have possibility optimize way. introduce implicit synchronisation points, may not want , canot control.
this not answer different aspect of question. part of "why need locking @ all". answer is, there no way around it. either need have lock somewhere, rely on atomic operations or disallow mutation altogether.
method 1 not feasible, have pointed out above, because loose potential optimization , have implicit synchronisation points.
only using atomic operations in data structure (i.e. non-locking structures) still open research question, , might not possible. know of non-locking structures, i.e. queues, lists etc, have never heard of non locking tree. non-locking structures tend become more complicated , slower, still need better structure thread local data, , can add these our datastructure zoo.
not having mutable datastructures @ in opinion best way of of them. mutability more of hassle worth. concept functional programming , makes sense in such environment. functional programming regarded esoteric concept programmers. languages used in production work use non-functional concepts (this not mean more complicated or more error prone, reflecting current state of training among developers). in opinion functional programming become more wide spread, once people start note solves threading problems automatically in blink. several other languages borrowing functional languages, find next evolution of data structures.
Comments
Post a Comment