# HG changeset patch # User cannam # Date 1242305108 0 # Node ID 516c86946900bd7cc0c05854544c0f7deec21dad # Parent 2af6edd98dfac5784aea98f5312b6aa964055f15 * Pull out AsynchronousTask into its own header * Add a fixed-size block allocator based on FSBAllocator diff -r 2af6edd98dfa -r 516c86946900 qm-dsp.pro --- a/qm-dsp.pro Wed May 13 17:41:10 2009 +0000 +++ b/qm-dsp.pro Thu May 14 12:45:08 2009 +0000 @@ -71,6 +71,8 @@ maths/MathUtilities.h \ maths/Polyfit.h \ maths/pca/pca.h \ + thread/AsynchronousTask.h \ + thread/BlockAllocator.h \ thread/Thread.h SOURCES += base/Pitch.cpp \ dsp/chromagram/Chromagram.cpp \ diff -r 2af6edd98dfa -r 516c86946900 thread/AsynchronousTask.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thread/AsynchronousTask.h Thu May 14 12:45:08 2009 +0000 @@ -0,0 +1,102 @@ +/* -*- c-basic-offset: 4 indent-tabs-mode: nil -*- vi:set ts=8 sts=4 sw=4: */ + +/* + QM DSP Library + + Centre for Digital Music, Queen Mary, University of London. + This file Copyright 2009 QMUL. +*/ + +#ifndef _ASYNCHRONOUS_TASK_H_ +#define _ASYNCHRONOUS_TASK_H_ + +#include "Thread.h" + +/** + * AsynchronousTask provides a thread pattern implementation for + * threads which are used to perform a series of similar operations in + * parallel with other threads of the same type. + * + * For example, a thread used to calculate FFTs of a particular block + * size in the context of a class that needs to calculate many block + * sizes of FFT at once may be a candidate for an AsynchronousTask. + * + * The general use pattern is: + * + * caller -> request thread A calculate something + * caller -> request thread B calculate something + * caller -> request thread C calculate something + * caller -> wait for threads A, B, and C + * + * Here threads A, B, and C may be AsynchronousTasks. An important + * point is that the caller must be prepared to block when waiting for + * these threads to complete (i.e. they are started asynchronously, + * but testing for completion is synchronous). + */ +class AsynchronousTask : public Thread +{ +public: + AsynchronousTask() : + m_todo("AsynchronousTask: task to perform"), + m_done("AsynchronousTask: task complete"), + m_inTask(false), + m_finishing(false) + { + start(); + } + virtual ~AsynchronousTask() + { + m_finishing = true; + m_todo.signal(); + wait(); + } + + // Subclass must provide methods to request task and obtain + // results, which the caller calls. The method that requests a + // new task should set up any internal state and call startTask(), + // which then calls back on the subclass implementation of + // performTask from within its work thread. The method that + // obtains results should call awaitTask() and then return any + // results from internal state. + +protected: + void startTask() { + m_todo.lock(); + m_inTask = true; + m_todo.signal(); + m_done.lock(); + m_todo.unlock(); + } + void awaitTask() { + while (m_inTask) m_done.wait(); + m_done.unlock(); + } + + virtual void performTask() = 0; + +private: + virtual void run() { + m_todo.lock(); + while (!m_finishing) { + while (!m_inTask && !m_finishing) { + m_todo.wait(); + } + if (m_finishing) { + break; + } + if (m_inTask) { + performTask(); + m_inTask = false; + m_done.signal(); + } + } + m_todo.unlock(); + } + + Condition m_todo; + Condition m_done; + bool m_inTask; + bool m_finishing; +}; + +#endif diff -r 2af6edd98dfa -r 516c86946900 thread/BlockAllocator.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/thread/BlockAllocator.h Thu May 14 12:45:08 2009 +0000 @@ -0,0 +1,189 @@ +/* -*- c-basic-offset: 4 indent-tabs-mode: nil -*- vi:set ts=8 sts=4 sw=4: */ + +/* + QM DSP Library + + Centre for Digital Music, Queen Mary, University of London. + + This file is derived from the FSB Allocator by Juha Nieminen. The + underlying method is unchanged, but the class has been refactored + to permit multiple separate allocators (e.g. one per thread) + rather than use a single global one (and to fit house style). + +Copyright (c) 2008 Juha Nieminen + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. +*/ + +#ifndef _BLOCK_ALLOCATOR_H_ +#define _BLOCK_ALLOCATOR_H_ + +#include + +/** + * BlockAllocator is a simple allocator for fixed-size (usually small) + * chunks of memory. The size of an element is specified in the + * BlockAllocator constructor, and the functions allocate() and + * deallocate() are used to obtain and release a single element at a + * time. + * + * BlockAllocator may be an appropriate class to use in situations + * involving a very large number of allocations and deallocations of + * simple, identical objects across multiple threads (a hard situation + * for a generic system malloc implementation to handle well). Retain + * one BlockAllocator per thread (the class itself is not + * thread-safe), and ensure that each thread uses its own allocator + * exclusively. + * + * BlockAllocator is based on Juha Nieminen's more general + * FSBAllocator. + */ +class BlockAllocator +{ +public: + typedef std::size_t data_t; + + BlockAllocator(int elementSize) : m_sz(elementSize) { } + + void * + allocate() + { + if (m_freelist.empty()) { + m_freelist.push_back(m_blocks.data.size()); + m_blocks.data.push_back(Block(this)); + } + + const data_t index = m_freelist.back(); + Block &block = m_blocks.data[index]; + void *retval = block.allocate(index); + if (block.isFull()) m_freelist.pop_back(); + + return retval; + } + + void + deallocate(void *ptr) + { + if (!ptr) return; + + data_t *unitPtr = (data_t *)ptr; + const data_t blockIndex = unitPtr[elementSizeInDataUnits()]; + Block& block = m_blocks.data[blockIndex]; + + if (block.isFull()) m_freelist.push_back(blockIndex); + block.deallocate(unitPtr); + } + +private: + inline data_t elementsPerBlock() const { + return 512; + } + inline data_t dataSize() const { + return sizeof(data_t); + } + inline data_t elementSizeInDataUnits() const { + return (m_sz + (dataSize() - 1)) / dataSize(); + } + inline data_t unitSizeInDataUnits() const { + return elementSizeInDataUnits() + 1; + } + inline data_t blockSizeInDataUnits() const { + return elementsPerBlock() * unitSizeInDataUnits(); + } + + class Block + { + public: + Block(BlockAllocator *a) : + m_a(a), + m_block(0), + m_firstFreeUnit(data_t(-1)), + m_allocated(0), + m_end(0) + {} + + ~Block() { + delete[] m_block; + } + + bool isFull() const { + return m_allocated == m_a->elementsPerBlock(); + } + + void clear() { + delete[] m_block; + m_block = 0; + m_firstFreeUnit = data_t(-1); + } + + void *allocate(data_t index) { + + if (m_firstFreeUnit == data_t(-1)) { + + if (!m_block) { + m_block = new data_t[m_a->blockSizeInDataUnits()]; + m_end = 0; + } + + data_t *retval = m_block + m_end; + m_end += m_a->unitSizeInDataUnits(); + retval[m_a->elementSizeInDataUnits()] = index; + ++m_allocated; + return retval; + + } else { + + data_t *retval = m_block + m_firstFreeUnit; + m_firstFreeUnit = *retval; + ++m_allocated; + return retval; + } + } + + void deallocate(data_t *ptr) { + + *ptr = m_firstFreeUnit; + m_firstFreeUnit = ptr - m_block; + + if (--m_allocated == 0) clear(); + } + + private: + const BlockAllocator *m_a; + data_t *m_block; + data_t m_firstFreeUnit; + data_t m_allocated; + data_t m_end; + }; + + struct Blocks + { + std::vector data; + + Blocks() { + data.reserve(1024); + } + }; + + const int m_sz; + Blocks m_blocks; + std::vector m_freelist; +}; + +#endif diff -r 2af6edd98dfa -r 516c86946900 thread/Thread.h --- a/thread/Thread.h Wed May 13 17:41:10 2009 +0000 +++ b/thread/Thread.h Thu May 14 12:45:08 2009 +0000 @@ -146,65 +146,4 @@ #endif }; -class AsynchronousTask : public Thread -{ -public: - AsynchronousTask() : - m_todo("AsynchronousTask: task to perform"), - m_done("AsynchronousTask: task complete"), - m_inTask(false), - m_finishing(false) - { - start(); - } - virtual ~AsynchronousTask() - { - m_finishing = true; - m_todo.signal(); - wait(); - } - - // subclass must provide methods to request task and obtain - // results - -protected: - void startTask() { - m_todo.lock(); - m_inTask = true; - m_todo.signal(); - m_done.lock(); - m_todo.unlock(); - } - void awaitTask() { - while (m_inTask) m_done.wait(); - m_done.unlock(); - } - - virtual void performTask() = 0; - -private: - virtual void run() { - m_todo.lock(); - while (!m_finishing) { - while (!m_inTask && !m_finishing) { - m_todo.wait(); - } - if (m_finishing) { - break; - } - if (m_inTask) { - performTask(); - m_inTask = false; - m_done.signal(); - } - } - m_todo.unlock(); - } - - Condition m_todo; - Condition m_done; - bool m_inTask; - bool m_finishing; -}; - #endif