README
¶
dispatch version 0.0_5
Package dispatch provides goroutine dispatch and concurrency limiting
About dispatch
Package dispatch provides an object Dispatch which is a queueing system for concurrent functions. It implements a dynamic limit on the number of routines it is runs simultaneously. It also implements an interface Queue, allowing for alternate queue implementations.
Performance
Generally, you run concurrent processes for increased program speed. So, you would like a dispatch method to be fast. However, the general purpose nature of the dispatch package causes some necessary bloating underlying the methods of Dispatch objects. For concurrent tasks which are doing actual work for more than a few hundred nanoseconds, this should not be very noticeable.
Hovever, if you have very high performance expectations, you may be better off writing your own lean and mean goroutine dispatcher that is suited for your individual purposes.
Dependencies
You must have Go installed (http://golang.org/).
Documentation
Installation
Use goinstall to install godirs
goinstall github.com/bmatsuo/dispatch
Examples
You can usage examples by checking out the examples subdirectory. You can run the compile all the examples to run the locally with the following commands
cd $GOROOT/src/pkg/github.com/bmatsuo/dispatch
gomake exinstall
This installs all the examples. So, you can for instance run godu
simply with the command
godu
When you are done, remove the examples with the command
gomake exnuke
General Documentation
Use godoc to vew the documentation for dispatch
godoc github.com/bmatsuo/dispatch
Or alternatively, use a godoc http server
godoc -http=:6060
and view the url http://localhost:6060/pkg/github.com/bmatsuo/dispatch
Author
Bryan Matsuo bmatsuo@soe.ucsc.edu
Copyright & License
Copyright (c) 2011, Bryan Matsuo. All rights reserved.
Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
Documentation
¶
Overview ¶
Package queues defines the Queue interface used in package dispatch, and several Queue implementations.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type ArrayPriorityQueue ¶
type ArrayPriorityQueue struct {
// contains filtered or unexported fields
}
An array-based priority queue with a constant time dequeue and a linear time equeue. It should slightly outperform a VectorPriorityQueue, but will likely be removed from the library because it is requires more maintenance.
func NewArrayPriorityQueue ¶
func NewArrayPriorityQueue() *ArrayPriorityQueue
Create a new array-based priority queue.
func (*ArrayPriorityQueue) Dequeue ¶
func (apq *ArrayPriorityQueue) Dequeue() RegisteredTask
Remove the next task with a runtime O(1).
func (*ArrayPriorityQueue) Enqueue ¶
func (apq *ArrayPriorityQueue) Enqueue(task RegisteredTask)
Add a task to the queue with runtime O(n) (on average n/2 + log_2(n))
func (*ArrayPriorityQueue) Len ¶
func (apq *ArrayPriorityQueue) Len() int
The number of items in the queue.
func (*ArrayPriorityQueue) SetKey ¶
func (apq *ArrayPriorityQueue) SetKey(id int64, k float64)
Add a task to the queue with runtime O(n).
type FIFO ¶
type FIFO struct {
// contains filtered or unexported fields
}
A First In First Out (FIFO) Queue implemented as a circular slice.
func (*FIFO) Enqueue ¶
func (dq *FIFO) Enqueue(task RegisteredTask)
Add a task in O(1) amortized time.
type LIFO ¶
type LIFO struct {
// contains filtered or unexported fields
}
A Last In First Out (LIFO) Queue (also known as a stack) implemented with a slice.
func (*LIFO) Dequeue ¶
func (dq *LIFO) Dequeue() RegisteredTask
Dequeue (pop) a task off the LIFO in O(1) time.
func (*LIFO) Enqueue ¶
func (dq *LIFO) Enqueue(task RegisteredTask)
Enqueue (push) a task on the LIFO in O(1) amortized time.
type PrioritizedTask ¶
A PrioritizedTask is a Task that also has key (float64). Generally, a lower key means higher priority.
type PriorityQueue ¶
type PriorityQueue struct {
// contains filtered or unexported fields
}
A heap-based priority queue. This implementation of a priority queue is ideal for many situations involving a priority queue. However, other priority queue implementations exist, each with their strengths and weaknesses. See ArrayPriorityQueue and VectorPriorityQueue.
func NewPriorityQueue ¶
func NewPriorityQueue() *PriorityQueue
Create a new heap-based priority queue.
func (*PriorityQueue) Dequeue ¶
func (pq *PriorityQueue) Dequeue() RegisteredTask
Remove a task from the queue with runtime O(log(n)).
func (*PriorityQueue) Enqueue ¶
func (pq *PriorityQueue) Enqueue(task RegisteredTask)
Add a task to the queue with runtime O(log(n)). The Task() method of task must satisfy the PrioritizedTask interface, or a runtime panic is thrown.
func (*PriorityQueue) SetKey ¶
func (pq *PriorityQueue) SetKey(id int64, k float64)
Set a task's key with runtime O(n).
type Queue ¶
type Queue interface {
Enqueue(task RegisteredTask) // Insert a task
Dequeue() RegisteredTask // Remove the next task.
Len() int // Number of items waiting for processing.
SetKey(int64, float64) // Set a task's key (priority queues).
}
A Queue is a queue for RegisteredTasks, used by a Dispatch. Queue objects can be priority queues or not, but they all must implement a method SetKey(...). For non-priority queues, that method should just return immediately.
To avoid race conditions, when Queue methods are called by a Dispatch, the Dispatch locks the queue and prevents any other methods from being called on it. This is something to think about when creating/choosing a Queue implementation.
type RegisteredTask ¶
A Task given to a Dispatch is given a unique id and becomes a RegisteredTask.
type Task ¶
type Task interface {
SetFunc(func(id int64))
Func() func(id int64)
Type() string // Used mostly for debugging
}
A Task is the interface satisfied by objects passed to a Dispatch.
type VectorPriorityQueue ¶
type VectorPriorityQueue struct {
// contains filtered or unexported fields
}
A priority queue based on the "container/vector" package. This priority queue implementation has fast dequeues and slow enqueues.
func NewVectorPriorityQueue ¶
func NewVectorPriorityQueue() *VectorPriorityQueue
Create a new VectorPriorityQueue.
func (*VectorPriorityQueue) Dequeue ¶
func (vpq *VectorPriorityQueue) Dequeue() RegisteredTask
Remove the task with the smallest key in O(1) amortized time.
func (*VectorPriorityQueue) Enqueue ¶
func (vpq *VectorPriorityQueue) Enqueue(task RegisteredTask)
Add a task to the priority queue in O(n) time. This is done with a O(log(n)) binary search and an insert operation.
func (*VectorPriorityQueue) Len ¶
func (vpq *VectorPriorityQueue) Len() int
func (*VectorPriorityQueue) SetKey ¶
func (vpq *VectorPriorityQueue) SetKey(id int64, k float64)
Change the value of a task's key in O(n) time. This performs search, delete, and enqueue operations. Hence, this is not a fast method.
Source Files