I will continue to write in connection with Go's HTTP implementation. Today is about FIFO implementation. Click here for details (https://qiita.com/behiron/items/78d023be96058224e583#%E3%81%AF%E3%81%98%E3%82%81%E3%81%AB)
FFO implementation of HTTP client by Russ Cox was devised and was very interesting. Looking at the comments, it seems that it was a little devised based on Okazaki's purely functional queue.
This time, after touching them, I would like to implement FIFO in 5 ways with Go.
The implementation and test code can be found on GitHub.
I will introduce the implementation method. Here, for the sake of simplicity, I will introduce it based on the type name that I implemented.
The TwoListSlice implementation is almost copy and paste, so the implementation should be correct. Others are implemented without any reference, so there may be bugs. Not bad.
SList It's a very simple implementation, just a singly linked list. Each element holds a value and a link to the next element, and the list structure holds head and tail.
Since it is the most orthodox implementation, I will omit the explanation, but one point is that the link of the element returned at the time of PopFront is overwritten with nil. This is to be recovered by GC, and is based on Go's standard library doubly linked list implementation.
PList
This simply recreates the SList by copying all the elements at PushBack and PopFront.
As I wrote in Test Code for SList, SList is not persistent, so after assigning queue A to queue B, the operation of queue A affects queue B.
To simply avoid this, all elements are copied every time they are operated.
This implementation is obviously heavy and TwoList is a better implementation.
TwoList This is a persistent FIFO implementation introduced in Okazaki's purely functional queue.
I'm interested in books but I haven't read them. Purely Functional Data Structures in 20 minutes is very easy to understand, and I will leave the detailed explanation of TwoList to that.
If you only use TwoList, you can understand it in about 5 minutes. The banker queue is a bit difficult and I don't really understand it after that.
To briefly explain the essence, it has two cues internally. It has a queue starting with head and a queue starting with tail, and each is a singly linked list (unlike SList, which only needs to hold the first element of the list).
At the time of PushBack, it is inserted at the beginning (** not the end **) of the queue starting with tail. At the time of PopFront, it is acquired from the beginning of the queue starting with head, but if it is empty, the queue starting with tail is reversed, switched as the queue starting with head, and then acquired from the beginning.
Isn't this really persistent? ?? I felt deceived, but I understood that the point is, "To make it persistent, in the update operation, the data that can be traced from the original structure should not be updated."
At first glance, reversing seems to be disadvantageous in terms of computational complexity, but it is not. In addition, there are further improvements, and I think it would be good to look at the previous material.
NaiveListSlice It is an implementation that uses go's Slice instead of a list. It is persistent. It's simple enough, so I'll just put the code and omit the explanation.
package fifo
type NaiveListSlice []interface{}
func (l *NaiveListSlice) Len() int {
return len(*l)
}
func (l *NaiveListSlice) PushBack(v interface{}) {
*l = append(*l, v)
}
func (l *NaiveListSlice) PopFront() interface{} {
list := *l
v := list[0]
*l = list[1:]
return v
}
TwoListSlice This is the implementation used in HTTP Client FIFO Implementation by Russ Cox. I will post the comment of ^ as it is.
// A wantConnQueue is a queue of wantConns.
type wantConnQueue struct {
// This is a queue, not a deque.
// It is split into two stages - head[headPos:] and tail.
// popFront is trivial (headPos++) on the first stage, and
// pushBack is trivial (append) on the second stage.
// If the first stage is empty, popFront can swap the
// first and second stages to remedy the situation.
//
// This two-stage split is analogous to the use of two lists
// in Okasaki's purely functional queue but without the
// overhead of reversing the list when swapping stages.
head []*wantConn
headPos int
tail []*wantConn
}
As you can see from the comments, it uses two queues like TwoList, and it is realized by Slice. The point is
headPos to advance slice (do not do* l = list [1:]in NaiveListSlice)I thought. Note that as you can see from Test, this structure itself is ** not persistent **, so be careful.
This structure can be used more memory than a simple FIFO implementation like NaiveListSlice, and may be good if the PushBack / PopFront operations continue more than a certain number of times.
Consider the case where the very simple PushBack and PopFront alternate once and for all.
In the implementation of NaiveListSlice, memory allocation for one element occurs every time in append at the time of PushBack. I'm not familiar with the append implementation, but in my environment I reserved 1-> 2-> 4-> 8 memory, so that's a prerequisite.
In the TwoListSlice implementation, the memory for one element is allocated only for the first two PushBacks, and the allocated memory is used after that.
To put it the other way around, it cannot be persistent because it is reused.
TwoListSlice is used by the HTTP clients idleConnWait and connsPerHostWait.
Both are kept for each host to connect to (strictly speaking, connect Method Key). I will briefly explain each of them.
idleConnWait is a queue that waits for a connection that becomes an idle. Note that it is a waiting queue, not an idle connection pool.
The idle connection pool is limited by the overall limit MaxIdleConns (default 100) and the per-host limit MaxIdleConnsPerHost (default 2).
When the client makes a request, if it finds that an idle connection is not available, it PushBacks idleConnWait "information that it wants a connection" and then dial to the connection destination. Before receiving the result of dial, the waiting order in idleConnWait turns, and if an idle connection becomes available, it is used, and the connection of the dial result that is no longer needed is used. It will be reused for other requests as an idle connection. Otherwise, the connection resulting from dial is normally used for the request.
connsPerHostWait is easier. MaxConnsPerHost (default disabled) limits the number of connections per host, and if that limit is exceeded, pushBack is done to connsPerHostWait before attempting a connection. If the wait turns and you are allowed to try the connection, it will be PopFront.
So why did we use the TwoListSlice structure to implement these two FIFO queues?
I think that is because the memory is used up assuming that the number of requests is temporarily increased, PushBack and PopFront are performed continuously, and the queue is not easily emptied.
In fact, during the Initial Review of This Implementation, Russ Cox commented:
I wanted to do something that would work well for an extreme case where there are many requests queued up on a small per-host limit, so I was careful in how I wrote the wantConnQueue,
Actually, it's good, and I wanted to implement the banker queue and "implement FIFO in 6 ways", but the banker queue does not implement "lazy evaluation", "memoization", etc. as a function type. I gave up this time because it seemed a little difficult to do with Go.
I'm planning to implement a banker queue soon.