What are some of the uses of circular buffer?
循环缓冲区有哪些用途?
What are the benefits of using a circular buffer?
使用循环缓冲区有什么好处?
is it an alternative to double linked list?
它是双链表的替代品吗?
6 个解决方案
#1
27
I've used it for an in-memory log with a restricted size. For example, the application would write log entries while processing user requests. Whenever an exception occurred (that would be disruptive to the processing) the log records currently in memory would be dumped along with it.
我已将它用于内存日志,其大小有限。例如,应用程序将在处理用户请求时写入日志条目。每当发生异常时(这会对处理造成破坏),当前在内存中的日志记录将与其一起转储。
The benefit of a circular buffer is, that you don't need infinite amounts of memory, since older entries get overridden automatically. The "challange" is, that you need to find a suitable size for your usecase. In the example above, it would be very unfortunate when the log record with the most vital information about the exception would have already been overridden.
循环缓冲区的好处是,您不需要无限量的内存,因为较旧的条目会被自动覆盖。 “挑战”是,您需要为您的用例找到合适的尺寸。在上面的示例中,当具有关于异常的最重要信息的日志记录已经被覆盖时,将是非常不幸的。
Some systems/applications have tools to let you extract the current content of the buffer on demand, and not only when it would be extract automatically (if ever).
某些系统/应用程序具有工具,可让您按需提取缓冲区的当前内容,而不仅仅是在自动提取时(如果有的话)。
I believe ETW and the CLRs stress log, amongst many other system's kernel or highperformance trace/logging, are implemented that way.
我相信ETW和CLRs压力日志,以及许多其他系统的内核或高性能跟踪/日志记录,都是以这种方式实现的。
The concept of using such buffers for in-memory tracing/logging is actually pretty common (not to say that this is the only use - certainly not), because it is way faster than written records to a file/database that you might never be interested in unless an error occurs. And on a related note, it conserves harddisk space.
使用这种缓冲区进行内存中跟踪/日志记录的概念实际上很常见(并不是说这是唯一的用途 - 当然不是),因为它比文件/数据库的写入记录更快,你可能永远不会感兴趣,除非发生错误。在相关的说明中,它节省了硬盘空间。
#2
12
Circular buffers are good for serial data streams in embedded systems. Microcontrollers often have a UART to handle a serial byte coming in, these need to be stored in order and dealt with later (bytes often come in at a faster rate than they can be handled).
循环缓冲区适用于嵌入式系统中的串行数据流。微控制器通常有一个UART来处理进入的串行字节,这些需要按顺序存储并稍后处理(字节通常以比它们可以处理的更快的速率进入)。
The buffer effectively splits the timing-critical response required (when the bytes come in, in microseconds) to the non timing-critical response to the whole message (for example displaying the message which came in, in milliseconds), e.g.:
缓冲区有效地将所需的时序关键响应(当字节进入时,以微秒为单位)分解为对整个消息的非时序关键响应(例如显示以毫秒为单位的消息),例如:
1) Upon the receipt of a byte the UART can generate an interrupt to which the software responds by quickly taking the received byte and shoves it onto the end of the buffer.
1)收到一个字节后,UART可以通过快速获取接收到的字节并将其推送到缓冲区的末尾来产生软件响应的中断。
2) Background software routines can then regularly check if the buffer has anything in it yet and empty it as required.
2)然后,后台软件程序可以定期检查缓冲区中是否有任何内容,并根据需要清空它。
As the circular buffer size can be defined pre-compilation the size is then limited. This helps improve space efficiency and should eliminate memory corruption at a trade off to how many bytes can be received before data starts to become lost.
由于可以在预编译时定义循环缓冲区大小,因此大小受到限制。这有助于提高空间效率,并且应该消除内存损坏,以便在数据开始丢失之前可以接收多少字节。
#3
6
I know this is cheating, but wikipedia does have a very good explaination.
我知道这是作弊,但*确实有很好的解释。
http://en.wikipedia.org/wiki/Circular_buffer
http://en.wikipedia.org/wiki/Circular_buffer
A circular buffer, cyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams
循环缓冲区,循环缓冲区或环形缓冲区是一种数据结构,它使用单个固定大小的缓冲区,就好像它是端到端连接一样。这种结构很容易缓冲数据流
An example that could possibly use an overwriting circular buffer is with multimedia. If the buffer is used as the bounded buffer in the producer-consumer problem then it is probably desired for the producer (e.g., an audio generator) to overwrite old data if the consumer (e.g., the sound card) is unable to momentarily keep up. Another example is the digital waveguide synthesis method which uses circular buffers to efficiently simulate the sound of vibrating strings or wind instruments.
可能使用覆盖循环缓冲区的示例是多媒体。如果缓冲器在生产者 - 消费者问题中被用作有界缓冲器,那么如果消费者(例如,声卡)不能暂时跟上,那么生产者(例如,音频发生器)可能希望覆盖旧数据。 。另一个例子是数字波导合成方法,其使用循环缓冲器来有效地模拟振动弦或管乐器的声音。
With regards comparing to double-linked lists, I imagine it really does depend on what you are using the list for... Implementation of cirular buffers seems to be more complex, please (again) refer to the wiki page; this explains implementation, considerations etc and also shows example code.
关于与双链表的比较,我想它确实取决于你使用列表的内容...圆形缓冲区的实现似乎更复杂,请(再次)参考维基页面;这解释了实现,注意事项等,并且还显示了示例代码。
Thanks, Neil
谢谢,尼尔
#4
5
A circular buffer is a nice mechanism for efficiently maintaining a sliding/moving list of values/items in an ordered fashion. One example might be to maintain a sliding average of the last N items. Suppose you want to track the average cost of the last 100 operations of computing some value. To do this, you would need to remove the oldest cost and add in the newest cost.
循环缓冲区是一种很好的机制,用于以有序的方式有效地维护滑动/移动的值/项列表。一个例子可能是维持最后N个项目的滑动平均值。假设您要跟踪计算某些值的最后100次操作的平均成本。为此,您需要删除最早的成本并添加最新的成本。
Without a circular buffer, a costly mechanism for doing this (C style) would be to have an array of 100 elements. Each time a new cost is computed, you could memmove the 99 elements down and put the new one in at the last position. This is obviously costly. Using a circular buffer idea, you would just track the “end” of the buffer (position 0-99). It would mark the position of the oldest (or newest … whichever you choose) cost item. After reading the old value (for updating the running average), you replace it with the newest value and increment the buffer position (if it is at 99, you set it back to 0 … thus, the circular part).
如果没有循环缓冲区,执行此操作(C样式)的昂贵机制将是具有100个元素的数组。每次计算新成本时,您都可以记下99个元素并将新元素放在最后一个位置。这显然是昂贵的。使用循环缓冲区构思,您只需跟踪缓冲区的“结束”(位置0-99)。它将标记最旧的(或最新的...无论您选择哪个)成本项目的位置。读取旧值(用于更新运行平均值)后,将其替换为最新值并增加缓冲区位置(如果为99,则将其设置为0 ...因此,圆形部分)。
Comparing it to a doubly linked list doesn’t really make sense. A circular buffer could certainly be implemented with a doubly linked list (or even a singly linked list). But comparing them is a little bit like comparing apples and oranges so to speak.
将它与双向链表进行比较并没有多大意义。一个循环缓冲区当然可以使用双向链表(甚至是单链表)来实现。但比较它们有点像比较苹果和橙子。
#5
0
I've used it as an easy way of implementing round-robin scheduling. Basically I had a bunch of different objects that can produce a value that a consumer could then process. I stuck all the producers in a ring and asked each one in turn.
我已经将它用作实现循环调度的简单方法。基本上我有一堆不同的对象可以产生一个消费者可以处理的价值。我把所有的制作人都放在一个戒指中,然后依次问每一个。
#6
0
I have used a ring buffer in multi-threaded code. Basically, if all slots are full the producer(s) have to wait. The consumers simply process items in slots that are "full".
我在多线程代码中使用了环形缓冲区。基本上,如果所有插槽都已满,则生产者必须等待。消费者只需处理“满”的插槽中的项目。
Here's a thread I started on it. It has some good advice on implementation.
这是我开始的一个主题。它对实施有一些很好的建议。
.NET multi-threaded variable access
.NET多线程变量访问
#1
27
I've used it for an in-memory log with a restricted size. For example, the application would write log entries while processing user requests. Whenever an exception occurred (that would be disruptive to the processing) the log records currently in memory would be dumped along with it.
我已将它用于内存日志,其大小有限。例如,应用程序将在处理用户请求时写入日志条目。每当发生异常时(这会对处理造成破坏),当前在内存中的日志记录将与其一起转储。
The benefit of a circular buffer is, that you don't need infinite amounts of memory, since older entries get overridden automatically. The "challange" is, that you need to find a suitable size for your usecase. In the example above, it would be very unfortunate when the log record with the most vital information about the exception would have already been overridden.
循环缓冲区的好处是,您不需要无限量的内存,因为较旧的条目会被自动覆盖。 “挑战”是,您需要为您的用例找到合适的尺寸。在上面的示例中,当具有关于异常的最重要信息的日志记录已经被覆盖时,将是非常不幸的。
Some systems/applications have tools to let you extract the current content of the buffer on demand, and not only when it would be extract automatically (if ever).
某些系统/应用程序具有工具,可让您按需提取缓冲区的当前内容,而不仅仅是在自动提取时(如果有的话)。
I believe ETW and the CLRs stress log, amongst many other system's kernel or highperformance trace/logging, are implemented that way.
我相信ETW和CLRs压力日志,以及许多其他系统的内核或高性能跟踪/日志记录,都是以这种方式实现的。
The concept of using such buffers for in-memory tracing/logging is actually pretty common (not to say that this is the only use - certainly not), because it is way faster than written records to a file/database that you might never be interested in unless an error occurs. And on a related note, it conserves harddisk space.
使用这种缓冲区进行内存中跟踪/日志记录的概念实际上很常见(并不是说这是唯一的用途 - 当然不是),因为它比文件/数据库的写入记录更快,你可能永远不会感兴趣,除非发生错误。在相关的说明中,它节省了硬盘空间。
#2
12
Circular buffers are good for serial data streams in embedded systems. Microcontrollers often have a UART to handle a serial byte coming in, these need to be stored in order and dealt with later (bytes often come in at a faster rate than they can be handled).
循环缓冲区适用于嵌入式系统中的串行数据流。微控制器通常有一个UART来处理进入的串行字节,这些需要按顺序存储并稍后处理(字节通常以比它们可以处理的更快的速率进入)。
The buffer effectively splits the timing-critical response required (when the bytes come in, in microseconds) to the non timing-critical response to the whole message (for example displaying the message which came in, in milliseconds), e.g.:
缓冲区有效地将所需的时序关键响应(当字节进入时,以微秒为单位)分解为对整个消息的非时序关键响应(例如显示以毫秒为单位的消息),例如:
1) Upon the receipt of a byte the UART can generate an interrupt to which the software responds by quickly taking the received byte and shoves it onto the end of the buffer.
1)收到一个字节后,UART可以通过快速获取接收到的字节并将其推送到缓冲区的末尾来产生软件响应的中断。
2) Background software routines can then regularly check if the buffer has anything in it yet and empty it as required.
2)然后,后台软件程序可以定期检查缓冲区中是否有任何内容,并根据需要清空它。
As the circular buffer size can be defined pre-compilation the size is then limited. This helps improve space efficiency and should eliminate memory corruption at a trade off to how many bytes can be received before data starts to become lost.
由于可以在预编译时定义循环缓冲区大小,因此大小受到限制。这有助于提高空间效率,并且应该消除内存损坏,以便在数据开始丢失之前可以接收多少字节。
#3
6
I know this is cheating, but wikipedia does have a very good explaination.
我知道这是作弊,但*确实有很好的解释。
http://en.wikipedia.org/wiki/Circular_buffer
http://en.wikipedia.org/wiki/Circular_buffer
A circular buffer, cyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams
循环缓冲区,循环缓冲区或环形缓冲区是一种数据结构,它使用单个固定大小的缓冲区,就好像它是端到端连接一样。这种结构很容易缓冲数据流
An example that could possibly use an overwriting circular buffer is with multimedia. If the buffer is used as the bounded buffer in the producer-consumer problem then it is probably desired for the producer (e.g., an audio generator) to overwrite old data if the consumer (e.g., the sound card) is unable to momentarily keep up. Another example is the digital waveguide synthesis method which uses circular buffers to efficiently simulate the sound of vibrating strings or wind instruments.
可能使用覆盖循环缓冲区的示例是多媒体。如果缓冲器在生产者 - 消费者问题中被用作有界缓冲器,那么如果消费者(例如,声卡)不能暂时跟上,那么生产者(例如,音频发生器)可能希望覆盖旧数据。 。另一个例子是数字波导合成方法,其使用循环缓冲器来有效地模拟振动弦或管乐器的声音。
With regards comparing to double-linked lists, I imagine it really does depend on what you are using the list for... Implementation of cirular buffers seems to be more complex, please (again) refer to the wiki page; this explains implementation, considerations etc and also shows example code.
关于与双链表的比较,我想它确实取决于你使用列表的内容...圆形缓冲区的实现似乎更复杂,请(再次)参考维基页面;这解释了实现,注意事项等,并且还显示了示例代码。
Thanks, Neil
谢谢,尼尔
#4
5
A circular buffer is a nice mechanism for efficiently maintaining a sliding/moving list of values/items in an ordered fashion. One example might be to maintain a sliding average of the last N items. Suppose you want to track the average cost of the last 100 operations of computing some value. To do this, you would need to remove the oldest cost and add in the newest cost.
循环缓冲区是一种很好的机制,用于以有序的方式有效地维护滑动/移动的值/项列表。一个例子可能是维持最后N个项目的滑动平均值。假设您要跟踪计算某些值的最后100次操作的平均成本。为此,您需要删除最早的成本并添加最新的成本。
Without a circular buffer, a costly mechanism for doing this (C style) would be to have an array of 100 elements. Each time a new cost is computed, you could memmove the 99 elements down and put the new one in at the last position. This is obviously costly. Using a circular buffer idea, you would just track the “end” of the buffer (position 0-99). It would mark the position of the oldest (or newest … whichever you choose) cost item. After reading the old value (for updating the running average), you replace it with the newest value and increment the buffer position (if it is at 99, you set it back to 0 … thus, the circular part).
如果没有循环缓冲区,执行此操作(C样式)的昂贵机制将是具有100个元素的数组。每次计算新成本时,您都可以记下99个元素并将新元素放在最后一个位置。这显然是昂贵的。使用循环缓冲区构思,您只需跟踪缓冲区的“结束”(位置0-99)。它将标记最旧的(或最新的...无论您选择哪个)成本项目的位置。读取旧值(用于更新运行平均值)后,将其替换为最新值并增加缓冲区位置(如果为99,则将其设置为0 ...因此,圆形部分)。
Comparing it to a doubly linked list doesn’t really make sense. A circular buffer could certainly be implemented with a doubly linked list (or even a singly linked list). But comparing them is a little bit like comparing apples and oranges so to speak.
将它与双向链表进行比较并没有多大意义。一个循环缓冲区当然可以使用双向链表(甚至是单链表)来实现。但比较它们有点像比较苹果和橙子。
#5
0
I've used it as an easy way of implementing round-robin scheduling. Basically I had a bunch of different objects that can produce a value that a consumer could then process. I stuck all the producers in a ring and asked each one in turn.
我已经将它用作实现循环调度的简单方法。基本上我有一堆不同的对象可以产生一个消费者可以处理的价值。我把所有的制作人都放在一个戒指中,然后依次问每一个。
#6
0
I have used a ring buffer in multi-threaded code. Basically, if all slots are full the producer(s) have to wait. The consumers simply process items in slots that are "full".
我在多线程代码中使用了环形缓冲区。基本上,如果所有插槽都已满,则生产者必须等待。消费者只需处理“满”的插槽中的项目。
Here's a thread I started on it. It has some good advice on implementation.
这是我开始的一个主题。它对实施有一些很好的建议。
.NET multi-threaded variable access
.NET多线程变量访问