我觉得有意思的学习内容

以前我一直认为自己对知识的渴望是纯粹的，认知、建模是我所有的意义。应试的学习让我感到不屑，却又因这份借口而无需过多进行实践

现在看来，对学习进步的需求无非来自三种追求：

• 获得知识本身
• 优越感
• 逃避劣等的恐惧

也许大部份人都有这些追求，只是不同的人和学习的内容，三种占比不同吧

我曾经自以为的纯粹知识渴望，也不过很大程度是对劣等感的逃避，为了没有胆量承认的虚荣

然而也许内心并不纯粹，追求俗不可耐，这样的自己才是真实的，而非想象中某种完美的幻影

无论出发点如何，如果还有兴趣能让我感到幸福，那便足够了吧 🙂

SplitArgs

• 把字符串根据空格/引号分割成多个 token
• 无引号 token 按照字面字符处理
• 单引号 token 仅 unescape '' -> '
• 双引号 token 按照 YAML 双引号字符串 unescape

FSM

Go 实现

这样用闭包按照我的理解应该不会有性能问题？可惜因为需要 unescape 无法做到 zero-allocation

const (
	splitArgsLookForToken int = iota
	splitArgsInToken
	splitArgsInSingleQuotes
	splitArgsInDoubleQuotes
	splitArgsSingleQuoteEscape
	splitArgsDoubleQuoteEscape
	splitArgsEndSuccess
	splitArgsEndFail
)

func SplitArgs(s string) (result []string, err error) {
	var sb strings.Builder
	var current rune
	var currentSize int
	var errMsg string
	peeked := false
	eoi := false
	idx := 0

	state := splitArgsLookForToken

	peek := func() {
		if peeked {
			return
		}
		peeked = true
		if idx >= len(s) {
			eoi = true
		} else {
			current, currentSize = utf8.DecodeRuneInString(s[idx:])
		}
	}

	peekHex := func(size int) error {
		if idx+size > len(s) {
			return errors.New("early EOI at index " + strconv.Itoa(idx))
		}

		r := rune(0)

		for i := range size {
			c := s[idx+i]
			var v rune
			switch {
			case c >= '0' && c <= '9':
				v = rune(c - '0')
			case c >= 'a' && c <= 'f':
				v = rune(c - 'a' + 10)
			case c >= 'A' && c <= 'F':
				v = rune(c - 'A' + 10)
			default:
				return errors.New("bad hex digit at index " + strconv.Itoa(idx+i))
			}
			r = (r << 4) | v
		}

		current = r
		currentSize = size
		return nil
	}

	// Must only be called after calling peek()
	pop := func() {
		idx += currentSize
		peeked = false
	}

	begin := func() {
		sb.Reset()
	}

	end := func() {
		result = append(result, sb.String())
	}

	// Must only be called after calling peek() and before calling pop()
	write := func() {
		sb.WriteRune(current)
	}

	for {
		switch state {
		case splitArgsEndFail:
			err = errors.New("SplitArgs: " + errMsg)
			fallthrough
		case splitArgsEndSuccess:
			return
		case splitArgsLookForToken:
			peek()
			if eoi {
				state = splitArgsEndSuccess
				continue
			}

			switch current {
			case '\t', '\n', '\v', '\f', '\r', ' ':
				pop()
				continue
			case '\'':
				pop()
				begin()
				state = splitArgsInSingleQuotes
				continue
			case '"':
				pop()
				begin()
				state = splitArgsInDoubleQuotes
				continue
			default:
				begin()
				state = splitArgsInToken
				continue
			}

		case splitArgsInToken:
			peek()

			if eoi {
				end()
				state = splitArgsEndSuccess
				continue
			}

			switch current {
			case '\t', '\n', '\v', '\f', '\r', ' ':
				pop()
				end()
				state = splitArgsLookForToken
				continue
			default:
				write()
				pop()
				continue
			}

		case splitArgsInSingleQuotes:
			peek()

			if eoi {
				errMsg = "early EOI at index " + strconv.Itoa(idx)
				state = splitArgsEndFail
				continue
			}

			switch current {
			case '\'':
				pop()
				state = splitArgsSingleQuoteEscape
				continue
			default:
				write()
				pop()
				continue
			}

		case splitArgsInDoubleQuotes:
			peek()

			if eoi {
				errMsg = "early EOI at index " + strconv.Itoa(idx)
				state = splitArgsEndFail
				continue
			}

			switch current {
			case '"':
				end()
				pop()
				state = splitArgsLookForToken
				continue
			case '\\':
				pop()
				state = splitArgsDoubleQuoteEscape
				continue
			default:
				write()
				pop()
				continue
			}

		case splitArgsSingleQuoteEscape:
			peek()

			if !eoi && current == '\'' {
				write()
				pop()
				state = splitArgsInSingleQuotes
				continue
			} else {
				end()
				state = splitArgsLookForToken
				continue
			}

		case splitArgsDoubleQuoteEscape:
			peek()

			if eoi {
				errMsg = "early EOI at index " + strconv.Itoa(idx)
				state = splitArgsEndFail
				continue
			}

			switch current {
			case '"', '\\', '/', ' ', '\x09':
				write()
				pop()
				state = splitArgsInDoubleQuotes
				continue
			case '0', 'a', 'b', 't', 'n', 'v', 'f', 'r', 'e', 'N', '_', 'L', 'P':
				switch current {
				case '0':
					current = '\x00'
				case 'a':
					current = '\a'
				case 'b':
					current = '\b'
				case 't':
					current = '\t'
				case 'n':
					current = '\n'
				case 'v':
					current = '\v'
				case 'f':
					current = '\f'
				case 'r':
					current = '\r'
				case 'e':
					current = '\x1b'
				case 'N':
					current = '\x85'
				case '_':
					current = '\xa0'
				case 'L':
					current = '\u2028'
				case 'P':
					current = '\u2029'
				}
				write()
				pop()
				state = splitArgsInDoubleQuotes
				continue
			case 'x', 'u', 'U':
				var size int
				switch current {
				case 'x':
					size = 2
				case 'u':
					size = 4
				case 'U':
					size = 8
				}
				pop()
				if err := peekHex(size); err != nil {
					errMsg = err.Error()
					state = splitArgsEndFail
					continue
				}

				write()
				pop()
				state = splitArgsInDoubleQuotes
				continue
			default:
				errMsg = "bad escape sequence at index " + strconv.Itoa(idx)
				state = splitArgsEndFail
				continue
			}

		default:
			errMsg = "internal error"
			state = splitArgsEndFail
			continue
		}
	}
}

感觉接口设计有点问题，似乎应该把 unescape 和 split 分开？ 🤔

才发现状态名写错了应该是 unescape

方法论

写这种复杂状态机之前，先用表格大致设计出状态和迁移会顺利很多

我第一次写 IP Prefix trie 的时候完全梦到哪写到哪，哪里有问题就多加一个分支，最后变得非常莫名其妙 😅

每过一两个月就觉得以前写的东西依托构使，恨不得狠狠 refactor 但是又没精力有没有懂的

Ring Buffer Read/Write

行为：

• 写入/读取 异步安全
• 读取时，如果有效数据不足，仅读取有效数据并报错
• 写入时，如果有效空间不足，仅写入有效空间并报错
• 保留 1 字节区分 完全空/完全满

结构体

type Ring struct {
	buffer []byte

	wp atomic.Int64 // write pointer
	_  [64 - 24 - 8]byte

	rp atomic.Int64 // read pointer
	_  [64 - 8]byte
}

读取

func (ring *Ring) Read(p []byte) (n int, err error) {
	wp := int(ring.wp.Load()) // Might be stale but it's ok
	rp := int(ring.rp.Load())

	defer func() {
		ring.rp.Store(int64(rp))
	}()

	// data size
	n = wp - rp
	if n < 0 {
		n += len(ring.buffer)
	}

	if n < len(p) {
		err = io.EOF // B, D
	} else {
		n = len(p) // A, C
	}

	if rem := n - copy(p[:n], ring.buffer[rp:]); rem > 0 {
		copy(p[n-rem:], ring.buffer[:rem]) // C, D
		rp = rem
	} else {
		rp += n // A, B
	}

	return
}

状态变量：

• EOF: len(p) 大于有效数据
• Wrap: 读取跨越切片结尾

A

0 1 2 3 4 5 6 7
x x o o #[x x]x
    ^     ^
    wp    rp

Read(p), len(p): 2

n = 2 - 5 + 8 = 5 > 2: n = 2
rem = 2 - copy(p[:2], buf[5:]) = 0
rp += 2 = 7

B

0 1 2 3 4 5 6 7
o #[x x x]o o o
    ^     ^
    rp    wp

Read(p), len(p): 4

n = 5 - 2 = 3 < 4: EOF
rem = 3 - copy(p[:3], buf[2:]) = 0
rp += 3 = 5

C

0 1 2 3 4 5 6 7
x]x o o #[x x x
    ^     ^
    wp    rp

Read(p), len(p): 4

n = 2 - 5 + 8 = 5 > 4: n = 4
rem = 4 - copy(p[:4], buf[5:]) = 1
copy(p[4-1:], buf[:1])
rp = 1

D

0 1 2 3 4 5 6 7
x]x o o #[x x x
    ^     ^
    wp    rp

Read(p), len(p): 6

n = 2 - 5 + 8 = 5 < 6: EOF
rem = 5 - copy(p[:5], buf[5:]) = 2
copy(p[5-2:], buf[:2])
rp = 2

写入

func (ring *Ring) Write(p []byte) (n int, err error) {
	rp := int(ring.rp.Load()) // Might be stale but it's ok
	wp := int(ring.wp.Load())

	defer func() {
		ring.wp.Store(int64(wp))
	}()

	// free space
	n = rp - wp - 1
	if n < 0 {
		n += len(ring.buffer)
	}

	if n < len(p) {
		err = ErrBufferFull // B, D
	} else {
		n = len(p) // A, C
	}

	if rem := n - copy(ring.buffer[wp:], p[:n]); rem > 0 {
		copy(ring.buffer[:rem], p[n-rem:]) // C, D
		wp = rem
	} else {
		wp += n // A, B
	}

	return
}

状态变量：

• Full: len(p) 大于有效空间
• Wrap: 写入跨越切片结尾

A

0 1 2 3 4 5 6 7
x x[o o]# x x x
    ^     ^
    wp    rp

Write(p), len(p): 2

n = 5 - 2 - 1 = 2 >= 2: n = 2
rem = 2 - copy(buf[2:], p[:2]) = 0
wp += 2 = 4

B

0 1 2 3 4 5 6 7
x x[o o]# x x x
    ^     ^
    wp    rp

Write(p), len(p): 4

n = 5 - 2 - 1 = 2 < 4: Full
rem = 2 - copy(buf[2:], p[:2]) = 0
wp += 2 = 4

C

0 1 2 3 4 5 6 7
o #[x x x]o o o
    ^     ^
    rp    wp

Write(p), len(p): 4

n = 2 - 5 - 1 + 8 = 4 >= 4: n = 4
rem = 4 - copy(p[:4], buf[5:]) = 1
copy(buf[:1], p[4-1:])
wp = 1

D

0 1 2 3 4 5 6 7
o #[x x x]o o o
    ^     ^
    rp    wp

Write(p), len(p): 6

n = 2 - 5 - 1 + 8 = 4 < 6: Full
rem = 4 - copy(p[:4], buf[5:]) = 1
copy(buf[:1], p[4-1:])
wp = 1

ID Counter

type IDCounter interface {
	GetID() uint64
}

行为：

• 异步安全
• 有限时间内 ID 唯一

SimpleIDCounter

type SimpleIDCounter struct{ atomic.Uint64 }

func (c *SimpleIDCounter) GetID() uint64 {
	return c.Add(1)
}

异步安全，uint64 可生成 1 << 64 个唯一 ID，高并发下由于锁竞争延迟线性提高

RandomShardedIDCounter

type shard struct {
	value atomic.Uint64
	_     [64 - 8]byte
}

type RandomShardedIDCounter struct {
	shards []shard
	mask   int
	shifts int
}

func NewRandomShardedIDCounter(n int) *RandomShardedIDCounter {
	if n <= 0 {
		n = 1
	}

	numShards := 1
	shifts := 1

	for numShards < n {
		numShards <<= 1
		shifts++
	}

	return &RandomShardedIDCounter{
		shards: make([]shard, numShards),
		mask:   numShards - 1,
		shifts: shifts,
	}
}

func (c *RandomShardedIDCounter) GetID() uint64 {
	idx := rand.Int() & c.mask

	val := c.shards[idx].value.Add(1)

	return (val << uint64(c.shifts)) | uint64(idx)
}

异步安全，用 shardIdx 作为 ID 低位，每个 shard 可连续生成 1 << (64 - bitWidth(shardIdx)) 个唯一 ID

用随机 shardIdx 均分请求到各 shard 缓解锁竞争

这里 rand 是 math/rand/v2，因为 v1 的全局函数是同步的

跑分

Sharded 2 <= GOMAXPROCS <= 4 突然很慢是怎么回事有没有懂的？ 🫠
pprof 我还不太能用明白

  Total:       2.23s      2.33s (flat, cum) 98.73%
     60            .          .           		mask:   numShards - 1, 
     61            .          .           		shifts: shifts, 
     62            .          .           	} 
     63            .          .           } 
     64            .          .            
     65         10ms       10ms           func (c *RandomShardedIDCounter) GetID() uint64 { 
     66         60ms      160ms           	idx := rand.Int() & c.mask 
     67            .          .            
     68         60ms       60ms           	val := c.shards[idx].value.Add(1) 
     69            .          .            
     70        2.10s      2.10s           	return (val << uint64(c.shifts)) | uint64(idx) 
     71            .          .           } 

何意味

Btw 上传 webp 似乎有问题，转换后的 avif 图片无法正确显示

我这边可以正常显示 😍

Log file change watcher

接口

type Change uint8

const (
	ChangeCreated Change = iota
	ChangeDeleted
	ChangeMoved
	ChangeModified
	ChangeTruncated
)

type Watcher interface {
	BlockUntilChange(ctx context.Context) (Change, error)
}

Polling 实现

package tail

import (
	"context"
	"os"
	"time"
)

var _ Watcher = (*PollWatcher)(nil)

type PollWatcher struct {
	interval time.Duration
	filepath string
	fi       os.FileInfo
	size     int64
	modified time.Time
}

func NewPollWatcher(path string, interval time.Duration) (*PollWatcher, error) {
	fi, err := os.Stat(path)
	if err != nil {
		if os.IsNotExist(err) {
			fi = nil
		} else {
			return nil, err
		}
	}

	pw := &PollWatcher{
		filepath: path,
		interval: interval,
		fi:       fi,
	}

	if fi != nil {
		pw.size = fi.Size()
		pw.modified = fi.ModTime()
	}

	return pw, nil
}

func (pw *PollWatcher) BlockUntilChange(ctx context.Context) (Change, error) {
	ticker := time.NewTicker(pw.interval)
	defer ticker.Stop()

	for {
		select {
		case <-ctx.Done():
			return 0, ctx.Err()
		case <-ticker.C:
			fi, err := os.Stat(pw.filepath)
			if err != nil {
				if os.IsNotExist(err) {
					if pw.fi != nil {
						pw.fi = nil
						return ChangeDeleted, nil
					}
					continue
				}
				return 0, err
			}

			lastSize := pw.size
			lastModified := pw.modified
			lastFi := pw.fi
			pw.size = fi.Size()
			pw.modified = fi.ModTime()
			pw.fi = fi

			if lastFi == nil {
				return ChangeCreated, nil
			}

			if !os.SameFile(lastFi, fi) {
				return ChangeMoved, nil
			}

			if pw.size < lastSize {
				return ChangeTruncated, nil
			}

			if pw.size > lastSize || !pw.modified.Equal(lastModified) {
				return ChangeModified, nil
			}
		}
	}
}

刚才那是 png，这个能显示吗？

这里如果在一次迭代期间，截短并写入超过原来文件大小的内容，会误判为 ChangeModified，暂时想不到怎么办 🫠 （不过这种情况对于日志来说不太可能？）

后果是丢失一部分行

FSNotify 实现

package tail

import (
	"context"
	"errors"
	"fmt"
	"os"
	"path/filepath"

	"github.com/fsnotify/fsnotify"
)

var _ Watcher = (*FSNotifyWatcher)(nil)

type FSNotifyWatcher struct {
	watcher    *fsnotify.Watcher
	filepath   string
	size       int64
	wasPresent bool
}

func NewFSNotifyWatcher(path string) (*FSNotifyWatcher, error) {
	watcher, err := fsnotify.NewWatcher()
	if err != nil {
		return nil, err
	}

	cleanPath := filepath.Clean(path)
	parentDir := filepath.Dir(cleanPath)

	// Watch parent and filter by Event.Name
	err = watcher.Add(parentDir)
	if err != nil {
		watcher.Close()
		return nil, err
	}

	// Get initial size and presence
	var size int64
	wasPresent := false
	fi, err := os.Stat(path)
	if err == nil {
		size = fi.Size()
		wasPresent = true
	}

	return &FSNotifyWatcher{
		watcher:    watcher,
		filepath:   cleanPath,
		size:       size,
		wasPresent: wasPresent,
	}, nil
}

func (fw *FSNotifyWatcher) Close() error {
	return fw.watcher.Close()
}

func (fw *FSNotifyWatcher) BlockUntilChange(ctx context.Context) (Change, error) {
	for {
		select {
		case <-ctx.Done():
			return 0, ctx.Err()

		case err, ok := <-fw.watcher.Errors:
			if !ok {
				return 0, errors.New("watcher channel closed")
			}
			return 0, err

		case event, ok := <-fw.watcher.Events:
			if !ok {
				return 0, errors.New("watcher channel closed")
			}

			if filepath.Clean(event.Name) != fw.filepath {
				continue
			}

			switch {
			case event.Has(fsnotify.Create):
				if fw.wasPresent {
					if fi, err := os.Stat(fw.filepath); err == nil {
						fw.size = fi.Size()
					}
					continue
				}
				fw.wasPresent = true
				return ChangeCreated, nil

			case event.Has(fsnotify.Write):
				if fi, err := os.Stat(fw.filepath); err == nil {
					lastSize := fw.size
					fw.size = fi.Size()

					if fw.size < lastSize {
						return ChangeTruncated, nil
					} else {
						return ChangeModified, nil
					}
				} else {
					return 0, fmt.Errorf("os.Stat failed: %w", err)
				}

			case event.Has(fsnotify.Remove):
				fw.wasPresent = false
				return ChangeDeleted, nil

			case event.Has(fsnotify.Rename):
				return ChangeMoved, nil
			}
		}
	}
}

能正常显示。所有的图片除了svg之外，不管是什么格式，都会被ImageMagick转换为AVIF格式。如果没法正常显示，可能是浏览器不支持： AVIF image format | Can I use... Support tables for HTML5, CSS3, etc

其实普遍的做法是根据不同的浏览器UserAgent，服务器发送支持的格式。

另外AVIF虽然压缩率比较高，浏览器广泛支持，但也存在一些问题：

• 压缩/转码成avif较慢。
• 不支持progrssive decoding，导致没法在网络较慢时像jpg一样一行一行地加载，只能全部下载后才能加载。

比较理想的是jpeg-xl，支持progressive decoding, encoding较快。
但是目前仅支持最新版Chrome/Firefox并需要启用experimental setting：

• Chrome：
  访问 chrome://flags/
  enable-jxl-image-format
• Firefox：
  访问 about:config
  image.jxl.enabled

现在可以了，之前疑似没加载出来

不过之前确实上传 webp 无法立即显示，但是 png 可以

现在无法复现了

Edit: 编辑器内上传图片无法立即加载，手动在新标签页访问图片路径后就可以在编辑器内显示了，不知道是不是网络问题

Tail

package tail

import (
	"bufio"
	"bytes"
	"context"
	"errors"
	"fmt"
	"io"
	"os"
	"sync"
	"time"
)

const (
	pollInterval = 250 * time.Millisecond
)

type fakeReader struct{}

func (*fakeReader) Read(p []byte) (n int, err error) {
	return 0, nil
}

type Config struct {
	// Seek to before tailing.
	Seek SeekInfo

	// Provide appended data as the file grows.
	Follow bool

	// Keep trying to open a file if it is inaccessible.
	// Ignored when Follow is false.
	Retry bool

	// Use PollWatcher for file changes.
	// FSNotifyWatcher is used if false.
	Poll bool

	// Disable seeking.
	// Enable this for named pipes (mkfifo).
	NoSeek bool

	// Line delimiter.
	Delimiter byte
}

func DefaultConfig() Config {
	return Config{
		Delimiter: '\n',
	}
}

// SeekInfo
type SeekInfo struct {
	Offset int64
	Whence int
}

type Tail struct {
	cfg      Config
	filename string
	file     *os.File
	watcher  Watcher

	reader *bufio.Reader

	firstOpen bool

	mu     sync.Mutex
	ctx    context.Context
	cancel context.CancelFunc
}

func New(ctx context.Context, filename string, cfg Config) (*Tail, error) {

	var watcher Watcher
	var err error
	if cfg.Poll {
		watcher, err = NewPollWatcher(filename, pollInterval)
		if err != nil {
			return nil, fmt.Errorf("failed to create PollWatcher: %w", err)
		}
	} else {
		watcher, err = NewFSNotifyWatcher(filename)
		if err != nil {
			return nil, fmt.Errorf("failed to create FSNotifyWatcher: %w", err)
		}
	}

	return newTailWithWatcher(ctx, filename, cfg, watcher), nil
}

func newTailWithWatcher(ctx context.Context, filename string, cfg Config, watcher Watcher) *Tail {
	ctx, cancel := context.WithCancel(ctx)

	return &Tail{
		cfg:       cfg,
		filename:  filename,
		watcher:   watcher,
		reader:    bufio.NewReader(&fakeReader{}),
		firstOpen: true,
		ctx:       ctx,
		cancel:    cancel,
	}
}

var (
	ErrBufferTooShort = errors.New("buffer is too short to read complete line")
)

func (t *Tail) ReadLine(b []byte) (n int, err error) {
	t.mu.Lock()
	defer t.mu.Unlock()

	for {
		// Try to read a complete line already in the buffer
		if t.file != nil {
			n, found, err := t.tryReadLine(b)
			if found || err != nil {
				return n, err
			}
			// No complete line in buffer
			if !t.cfg.Follow {
				return 0, io.EOF
			}
		}

		// Eagerly open file
		if t.file == nil && !t.cfg.Follow {
			if err := t.openFile(); err == nil {
				continue
			}
		}

		// Wait for next file change
		ch, bErr := t.watcher.BlockUntilChange(t.ctx)
		if bErr != nil {
			return 0, bErr
		}

		fileWasOpen := t.file != nil

		if t.file == nil {
			if ch != ChangeDeleted {
				err = t.openFile()
				if err != nil {
					if t.cfg.Retry && t.cfg.Follow {
						continue
					}
					return
				}
			} else {
				continue
			}
		}

		switch ch {
		case ChangeCreated:
			if fileWasOpen {
				err = t.reopenFile()
				if err != nil {
					return
				}
			}
		case ChangeDeleted:
			err = t.closeFile()
			if err != nil {
				return
			}
		case ChangeModified:
			t.reader.Reset(t.file)
		case ChangeTruncated:
			if !t.cfg.NoSeek {
				_, err = t.file.Seek(0, io.SeekStart)
				if err != nil {
					return
				}
			}
		}
	}
}

func (t *Tail) tryReadLine(b []byte) (n int, found bool, err error) {
	nBuf := t.reader.Buffered()
	if nBuf == 0 {
		if _, err := t.reader.Peek(1); err != nil {
			if errors.Is(err, io.EOF) {
				return 0, false, nil
			}
			return 0, false, err
		}
		nBuf = t.reader.Buffered()
	}

	peeked, err := t.reader.Peek(nBuf)
	if err != nil && !errors.Is(err, io.EOF) {
		return 0, false, err
	}

	idx := bytes.IndexByte(peeked, t.cfg.Delimiter)
	if idx < 0 {
		return 0, false, nil
	}

	if len(b) < idx {
		return 0, false, ErrBufferTooShort
	}

	copied := copy(b, peeked[:idx])
	t.reader.Discard(idx + 1)
	return copied, true, nil
}

func (t *Tail) Close() error {
	t.cancel()
	return t.closeFile()
}

func (t *Tail) closeFile() (err error) {
	if t.file != nil {
		err = t.file.Close()
		t.file = nil
	}
	return
}

func (t *Tail) openFile() error {
	file, err := os.Open(t.filename)
	if err != nil {
		return err
	}

	if !t.cfg.NoSeek && t.firstOpen {
		if _, err := file.Seek(t.cfg.Seek.Offset, t.cfg.Seek.Whence); err != nil {
			file.Close()
			return err
		}
	}
	t.firstOpen = false

	t.file = file
	t.reader.Reset(t.file)
	return nil
}

func (t *Tail) reopenFile() (err error) {
	err = t.closeFile()
	if err != nil {
		return
	}
	err = t.openFile()
	return
}

合并了 ChangeMoved 和 ChangeDeleted（全部当作 ChangeDeleted）

FSM

ref: GitHub - nxadm/tail: [Revamped] Go package for reading from continuously updated files (tail -f)

好复杂，能 syslog over UDP 就别搞这种（

Minor issue

已配置，刷新一下

我是垃圾桶，这写的就是垃圾

重构

package tail

import (
	"bufio"
	"bytes"
	"context"
	"errors"
	"fmt"
	"io"
	"os"
	"sync"
	"time"
)

const (
	pollInterval = 250 * time.Millisecond
)

type fakeReader struct{}

func (*fakeReader) Read(p []byte) (n int, err error) {
	return 0, nil
}

type Config struct {
	// Seek to before tailing.
	Seek SeekInfo

	// Provide appended data as the file grows.
	Follow bool

	// Keep trying to open a file if it is inaccessible.
	// Requires Follow to be set.
	Retry bool

	// Use PollWatcher for file changes.
	// FSNotifyWatcher is used if false.
	Poll bool

	// Disable seeking.
	// Enable this for named pipes (mkfifo).
	NoSeek bool

	// MaxLineSize sets the maximum line length in bytes.
	// Lines exceeding this are returned in chunks of MaxLineSize with error ErrMaxLineSizeExceeded.
	// Defaults to 4096 when <= 0.
	MaxLineSize int

	// Line delimiter.
	Delimiter byte
}

func DefaultConfig() Config {
	return Config{
		Delimiter:   '\n',
		MaxLineSize: 4096,
	}
}

// SeekInfo
type SeekInfo struct {
	Offset int64
	Whence int
}

type tailState int8

const (
	stateInit tailState = iota
	stateReady
	stateEOF
	stateNotOpen
	stateFailed
)

type Tail struct {
	cfg      Config
	filename string

	file    *os.File
	watcher Watcher
	reader  *bufio.Reader

	state   tailState
	failErr error

	mu     sync.Mutex
	ctx    context.Context
	cancel context.CancelFunc
}

func New(ctx context.Context, filename string, cfg Config) (*Tail, error) {
	if !cfg.Follow && cfg.Retry {
		return nil, errors.New("Retry set without Follow")
	}

	var watcher Watcher
	var err error
	if cfg.Poll {
		watcher, err = NewPollWatcher(filename, pollInterval)
		if err != nil {
			return nil, fmt.Errorf("failed to create PollWatcher: %w", err)
		}
	} else {
		watcher, err = NewFSNotifyWatcher(filename)
		if err != nil {
			return nil, fmt.Errorf("failed to create FSNotifyWatcher: %w", err)
		}
	}

	return newTailWithWatcher(ctx, filename, cfg, watcher), nil
}

func newTailWithWatcher(ctx context.Context, filename string, cfg Config, watcher Watcher) *Tail {
	ctx, cancel := context.WithCancel(ctx)

	if cfg.MaxLineSize <= 0 {
		cfg.MaxLineSize = 4096
	}

	return &Tail{
		cfg:      cfg,
		filename: filename,
		watcher:  watcher,
		reader:   bufio.NewReaderSize(&fakeReader{}, cfg.MaxLineSize),
		state:    stateInit,
		ctx:      ctx,
		cancel:   cancel,
	}
}

var (
	ErrMaxLineSizeExceeded = errors.New("line exceeds MaxLineSize")
	ErrShortBuffer         = io.ErrShortBuffer
	ErrClosed              = errors.New("closed")
)

func (t *Tail) ReadLine(b []byte) (int, error) {
	t.mu.Lock()
	defer t.mu.Unlock()

	for {
		switch t.state {
		case stateInit:
			// Try to open file
			file, err := os.Open(t.filename)
			if err != nil {
				t.failErr = err
				t.state = stateNotOpen
				continue
			} else {
				if !t.cfg.NoSeek {
					_, err = file.Seek(t.cfg.Seek.Offset, t.cfg.Seek.Whence)
					if err != nil {
						t.failErr = err
						t.state = stateFailed
						return 0, err
					}
				}
				t.file = file
				t.reader.Reset(file)
				t.state = stateReady
				continue
			}

		case stateReady:
			// Try to read line
			n := t.reader.Buffered()
			if n == 0 {
				if _, err := t.reader.Peek(1); err != nil {
					if errors.Is(err, io.EOF) {
						t.state = stateEOF
						continue
					} else {
						t.failErr = err
						t.state = stateFailed
						return 0, err
					}
				}
				n = t.reader.Buffered()
			}

			peeked, err := t.reader.Peek(n)
			if err != nil && !errors.Is(err, io.EOF) {
				t.failErr = err
				t.state = stateFailed
				return 0, err
			}

			idx := bytes.IndexByte(peeked, t.cfg.Delimiter)
			if idx < 0 {
				// No delimiter found
				if n >= t.cfg.MaxLineSize {
					// Line exceeds MaxLineSize
					// Return chunk
					n = t.cfg.MaxLineSize
					if len(b) < n {
						return 0, ErrShortBuffer
					}
					peeked, _ = t.reader.Peek(n)
					copied := copy(b, peeked[:n])
					t.reader.Discard(n)
					return copied, ErrMaxLineSizeExceeded
				}
				t.state = stateEOF
				continue
			}

			// Delimiter found
			// Chunk if line exceeds MaxLineSize
			if idx >= t.cfg.MaxLineSize {
				n = t.cfg.MaxLineSize
				if len(b) < n {
					return 0, ErrShortBuffer
				}
				peeked, _ = t.reader.Peek(n)
				copied := copy(b, peeked[:n])
				t.reader.Discard(n)
				return copied, ErrMaxLineSizeExceeded
			}

			if len(b) < idx {
				return 0, ErrShortBuffer
			}

			copied := copy(b, peeked[:idx])
			t.reader.Discard(idx + 1)
			return copied, nil

		case stateEOF:
			if !t.cfg.Follow {
				n := t.reader.Buffered()
				if n > 0 {
					// Probe for more data
					_, peekErr := t.reader.Peek(n + 1)
					if errors.Is(peekErr, io.EOF) {
						// True EOF
						// Return as final line
						peeked, _ := t.reader.Peek(n)
						copied := copy(b, peeked[:n])
						t.reader.Discard(n)
						return copied, nil
					}
					if peekErr != nil {
						t.failErr = peekErr
						t.state = stateFailed
						return 0, peekErr
					}
					// Has more
					t.state = stateReady
					continue
				}
				t.failErr = io.EOF
				t.state = stateFailed
				return 0, io.EOF
			}

			ch, err := t.watcher.BlockUntilChange(t.ctx)
			if err != nil {
				t.failErr = err
				t.state = stateFailed
				return 0, err
			}

			switch ch {
			case ChangeModified, ChangeCreated:
				// Drain EOF error in bufio.Reader
				if n := t.reader.Buffered(); n > 0 && n < t.cfg.MaxLineSize {
					t.reader.Peek(n + 1) // trigger file read
				}
				t.state = stateReady
				continue
			case ChangeDeleted:
				// Drain buffer from old file
				if n := t.reader.Buffered(); n > 0 {
					if len(b) < n {
						return 0, ErrShortBuffer
					}
					peeked, _ := t.reader.Peek(n)
					copied := copy(b, peeked[:n])
					t.reader.Discard(n)
					t.file.Close()
					t.file = nil
					t.state = stateNotOpen
					return copied, nil
				}
				err = t.file.Close()
				if err != nil {
					t.failErr = err
					t.state = stateFailed
					return 0, err
				}
				t.file = nil
				t.state = stateNotOpen
				continue

			case ChangeTruncated:
				if !t.cfg.NoSeek {
					_, err := t.file.Seek(0, io.SeekStart)
					if err != nil {
						t.failErr = err
						t.state = stateFailed
						return 0, err
					}
				}
				t.reader.Reset(t.file)
				t.state = stateReady
				continue
			}

		case stateNotOpen:
			if !t.cfg.Retry {
				t.state = stateFailed
				return 0, errors.New("cannot open file")
			}

			ch, err := t.watcher.BlockUntilChange(t.ctx)
			if err != nil {
				t.failErr = err
				t.state = stateFailed
				return 0, err
			}

			switch ch {
			case ChangeCreated, ChangeModified, ChangeTruncated:
				// Try to open file
				file, err := os.Open(t.filename)
				if err != nil {
					continue
				} else {
					t.file = file
					t.reader.Reset(file)
					t.state = stateReady
					continue
				}

			case ChangeDeleted:
				t.failErr = errors.New("got ChangeDeleted in stateNotOpen")
				t.state = stateFailed
				return 0, t.failErr

			}

		case stateFailed:
			return 0, t.failErr
		}
	}
}

func (t *Tail) Close() error {
	t.cancel()
	t.mu.Lock()
	defer t.mu.Unlock()

	t.failErr = ErrClosed
	t.state = stateFailed
	if t.file != nil {
		if err := t.file.Close(); err != nil {
			return err
		}
	}
	return nil
}

go maps delete and clone

go maps 即使删除 kv pairs 也不会自动 shrink，如果长期使用同一 map 增删不同的 key 会导致 map 内存占用无限增长：

In the official standard Go runtime implementation, the backing array of a map will never shrink, even if all entries are deleted from the map. This is a form of memory wasting. But in practice, this is seldom a problem and and actually often good for program performances. - Maps -Go 101

vmstorage GC overhead grows on long running instance · Issue #5379 · VictoriaMetrics/VictoriaMetrics

解决方法是当 map 到达一定大小之后建立新 map 并复制所有 kv pairs：

		newCap := 0
		for _, idx := range s.idxMap {
			if isOneIterationBefore(idx, s.idx) {
				newCap++
			}
		}
		newMap := make(map[uint64]uint32, newCap)
		for k, idx := range s.idxMap {
			if isOneIterationBefore(idx, s.idx) {
				newMap[k] = idx
			}
		}
		s.idxMap = newMap

这里计算需要保留的 kv pair 个数并以此为 capacity hint 建立新 map

但是这样每次重建可能过于激进，产生更多 GC 压力

     71            .          .           		newCap := 0 
     72            .          .           		for _, idx := range s.idxMap { 
     73            .          .           			if isOneIterationBefore(idx, s.idx) { 
     74            .          .           				newCap++ 
     75            .          .           			} 
     76            .          .           		} 
     77     161.71MB   161.71MB           		newMap := make(map[uint64]uint32, newCap) 
     78            .          .           		for k, idx := range s.idxMap { 
     79            .          .           			if isOneIterationBefore(idx, s.idx) { 
     80       3.50MB     3.50MB           				newMap[k] = idx 
     81            .          .           			} 
     82            .          .           		} 

设置一个 mapResizeFactor，当 cap > use*factor 时才重建

		oldCap := len(s.idxMap)
		newCap := 0
		for _, idx := range s.idxMap {
			if isOneIterationBefore(idx, s.idx) {
				newCap++
			}
		}
		if oldCap >= newCap*mapResizeFactor {
			newMap := make(map[uint64]uint32, newCap)
			for k, idx := range s.idxMap {
				if isOneIterationBefore(idx, s.idx) {
					newMap[k] = idx
				}
			}
			s.idxMap = newMap
		} else {
			maps.DeleteFunc(s.idxMap, func(k uint64, idx uint32) bool {
				return !isOneIterationBefore(idx, s.idx)
			})
		}

另外这里需要遍历旧 map 两遍，因为先删除不需要的 kv pairs 更低效，而且删除后再复制本质上还是复制所有的 kv pairs 到新 map

如果使用 maps.Clone 就无法达到缩小 map 的效果，因为 maps.Clone 是链接到 runtime 包的实现，直接复制了原 map 的内存结构

// clone is implemented in the runtime package.
//
//go:linkname clone maps.clone
func clone(m any) any

// Clone returns a copy of m.  This is a shallow clone:
// the new keys and values are set using ordinary assignment.
func Clone[M ~map[K]V, K comparable, V any](m M) M {
	// Preserve nil in case it matters.
	if m == nil {
		return nil
	}
	return clone(m).(M)
}

// mapclone for implementing maps.Clone
//
//go:linkname mapclone maps.clone
func mapclone(m any) any {
	e := efaceOf(&m)
	typ := (*abi.MapType)(unsafe.Pointer(e._type))
	map_ := (*maps.Map)(e.data)
	map_ = map_.Clone(typ)
	e.data = (unsafe.Pointer)(map_)
	return m
}

func (m *Map) Clone(typ *abi.MapType) *Map {
	// Note: this should never be called with a nil map.
	if m.writing != 0 {
		fatal("concurrent map clone and map write")
	}

	// Shallow copy the Map structure.
	m2 := new(Map)
	*m2 = *m
	m = m2

	// We need to just deep copy the dirPtr field.
	if m.dirPtr == nil {
		// delayed group allocation, nothing to do.
	} else if m.dirLen == 0 {
		// Clone one group.
		oldGroup := groupReference{data: m.dirPtr}
		newGroup := groupReference{data: newGroups(typ, 1).data}
		cloneGroup(typ, newGroup, oldGroup)
		m.dirPtr = newGroup.data
	} else {
		// Clone each (different) table.
		oldDir := unsafe.Slice((**table)(m.dirPtr), m.dirLen)
		newDir := make([]*table, m.dirLen)
		for i, t := range oldDir {
			if i > 0 && t == oldDir[i-1] {
				newDir[i] = newDir[i-1]
				continue
			}
			newDir[i] = t.clone(typ)
		}
		m.dirPtr = unsafe.Pointer(&newDir[0])
	}

	return m
}

完蛋力，我是傻逼，以前写 sync.Pool 都写错了 😭

We’re using a pool of []byte. Generally (though not always), when you pass a value to an interface, it may cause the value to be placed on the heap. This happens here too, not just with slices but with anything you pass to pool.Put() that isn’t a pointer.
- Go sync.Pool and the Mechanics Behind It

var bufPool = sync.Pool{
	New: func() any {
		// The Pool's New function should generally only return pointer
		// types, since a pointer can be put into the return interface
		// value without an allocation:
		return new(bytes.Buffer)
	},
}

go/src/sync/example_pool_test.go at 2580d0e08d5e9f979b943758d3c49877fb2324cb · golang/go

大于 8 byte 的类型赋值到接口类型都会逃逸到堆，产生堆分配

可以使用 go 编译器进行逃逸分析：

go build -gcflags="-m" /path/to/src.go

sync.Pool 案例分析

slice.go - 切片池

package heaptest

import "sync"

var slicePool = sync.Pool{
	New: func() any {
		return make([]byte, 10)
	},
}

func getSlice() []byte {
	return slicePool.Get().([]byte)
}

func putSlice(s []byte) {
	slicePool.Put(s)
}

./slice.go:7:14: make([]byte, 10) escapes to heap
./slice.go:15:15: leaking param: s
./slice.go:16:16: s escapes to heap

这里 slicePool.Put(s) 会产生一次堆分配，因为 slice header 有 24 bytes，无法放入接口类型

slicePtr.go - 切片指针池

package heaptest

import "sync"

var slicePtrPool = sync.Pool{
	New: func() any {
		b := make([]byte, 10)
		return &b
	},
}

func getPtrSlice() *[]byte {
	return slicePtrPool.Get().(*[]byte)
}

func putPtrSlice(s *[]byte) {
	slicePtrPool.Put(s)
}

./slicePtr.go:7:3: moved to heap: b
./slicePtr.go:7:12: make([]byte, 10) escapes to heap
./slicePtr.go:16:18: leaking param: s

这样 slice header 和 slice 本身都分配在堆上，Put 时仅储存 slice header 指针（8 byte）

map.go - 表池

package heaptest

import "sync"

var mapPool = sync.Pool{
	New: func() any {
		return make(map[int]int)
	},
}

func getMap() map[int]int {
	return mapPool.Get().(map[int]int)
}

func putMap(m map[int]int) {
	clear(m)
	mapPool.Put(m)
}

./map.go:7:14: make(map[int]int) escapes to heap
./map.go:15:13: leaking param: m

map 类型本来就是指向 map 内容的指针，所以可以直接赋值给接口类型无需堆分配
类似的 chan, func() 也是指针所以也可以高效赋值给接口类型

跑分

错误写法

goos: linux
goarch: amd64
pkg: github.com/HT4w5/kv
cpu: Intel(R) Core(TM) Ultra 9 185H
=== RUN   BenchmarkCacheSetDelete
BenchmarkCacheSetDelete
=== RUN   BenchmarkCacheSetDelete/Size-33554432
BenchmarkCacheSetDelete/Size-33554432
BenchmarkCacheSetDelete/Size-33554432-22                53940969                22.58 ns/op      708.57 MB/s          30 B/op          0 allocs/op
=== RUN   BenchmarkCacheSetDelete/Size-1073741824
BenchmarkCacheSetDelete/Size-1073741824
BenchmarkCacheSetDelete/Size-1073741824-22              61089979                16.99 ns/op      941.60 MB/s          24 B/op          1 allocs/op
PASS
ok      github.com/HT4w5/kv     2.310s

正确写法

goos: linux
goarch: amd64
pkg: github.com/HT4w5/kv
cpu: Intel(R) Core(TM) Ultra 9 185H
=== RUN   BenchmarkCacheSetDelete
BenchmarkCacheSetDelete
=== RUN   BenchmarkCacheSetDelete/Size-33554432
BenchmarkCacheSetDelete/Size-33554432
BenchmarkCacheSetDelete/Size-33554432-22                91227044                13.39 ns/op     1194.55 MB/s           0 B/op          0 allocs/op
=== RUN   BenchmarkCacheSetDelete/Size-1073741824
BenchmarkCacheSetDelete/Size-1073741824
BenchmarkCacheSetDelete/Size-1073741824-22              116488242               10.45 ns/op     1531.02 MB/s           0 B/op          0 allocs/op
PASS
ok      github.com/HT4w5/kv     3.400s

才发现 Go atomic.Uint64 只有 Add() 没有 Sub() 所以想减只能 Add(^uint64(delta - 1)) 🤯

有意思的：

• 泛型方法
• uuid
• json/v2
• simd

造轮子笑传之 chunked cache bucket

起因是我需要 fastcache，但是 fastcache 没有迭代器，所以干脆自己仿制一个就当学习了

Public Interface

 type Cache
    func New(size int) *Cache
    func (c *Cache) Del(k []byte)
    func (c *Cache) Get(dst, k []byte) (res []byte)
    func (c *Cache) Has(k []byte) (found bool)
    func (c *Cache) HasGet(dst, k []byte) (res []byte, found bool)
    func (c *Cache) Iterator() *Iterator
    func (c *Cache) LoadStats(stats *Stats)
    func (c *Cache) Reset()
    func (c *Cache) Set(k, v []byte)
type Iterator
    func (it *Iterator) GetNext(kDst, vDst []byte) ([]byte, []byte, bool)
type Stats

架构

┌─────────────────┐ ┌─────────────────┐ ┌─────────────────┐
│                 │ │ map[hash]idx    │ │                 │
│ [512]bucket◄────┼─┤ [n]chunks◄──────┼─┤ [65536]byte     │
│                 │ │     idx         │ │   useCount      │
└─────────────────┘ └─────────────────┘ └─────────────────┘
      cache               bucket              chunk        

• Cache 分 512 个 bucket，每个 bucket 有独立的读写锁
• 每个 bucket 是由 n 个 chunk 构成的 ring buffer，idx 记录下一次写入位置，map[hash]idx 记录现有键值对位置
• 每个 chunk 是 [65536]byte
• n 可根据 Cache 大小进行调整，至少为 1，整个 Cache 至少 65536*1*512 B = 32 MiB

键值对格式

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|          kLen (uint16le)      |          vLen (uint16le)      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
+                        k (kLen bytes)                         +
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
+                        v (vLen bytes)                         +
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

• 键值对不可跨 chunk 存在，键值对记录最长为 65536 bytes,因此 kLen, vLen 可用 uint16 记录

idx 格式

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|W|                     chunkIndex (47 bits)                    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|     chunkIndex (cont.)        |      localIndex (16 bits)     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

• W: wrap，ring 每走一圈翻转一次
• chunkIndex: chunk 编号
• localIndex: chunk 上的 byte 编号
• 对给定的 idxA, idxB，若 idxA 为键值对 idx，idxB 为 bucket.idx，判断 idxA 键值对仍有效（未被 ring 写入覆盖）的方法：int64(idxA - idxB) < 0 (isValid).

写入流程

1. Set(k, v []byte) 得到待写入键值对
2. 计算 hash = xxhash3(k)
3. 计算 bucket 编号 bktIdx = hash%512，对 bucket[bktIdx] 进行操作
4. 获取 bucket 写入锁
5. 检查 hash 是否已存在 map 中，如果是，使旧键值对所在 chunk.useCount--，若归零则将 chunk 放回 chunkPool
6. 检查 idx 能否写入键值对:
   1. 若当前 chunk 剩余空间足以写入键值对记录，则下一步
   2. 若当前 chunk 剩余空间不足:
      1. 若当前 chunk 非最后一个，前进至下一 chunk 并下一步
      2. 若当前 chunk 是最后一个，回到第一个 chunk，翻转 idx.W，清除 map 中所有被覆盖键值对记录（根据 isValid 判断，删除键值对记录同时所在 chunk.useCount--，若归零则将 chunk 放回 chunkPool），再下一步
7. 若当前 chunk 未 allocate: 从 chunkPool 获取空闲 chunk 并分配给当前位置
8. 写入
9. 更新 bucket.idx

读取流程

1. Get(dst, k []byte) 得到键
2. 计算 hash = xxhash3(k)
3. 计算 bucket 编号 bktIdx = hash%512，对 bucket[bktIdx] 进行操作
4. 获取 bucket 读取锁
5. 检查 hash 是否在 map 中，若在则下一步，否则 miss
6. 根据 isValid 检查 idx 是否有效，若无效则 miss
7. 根据 idx 计算 chunkIdx, localIdx
8. 读取 kLen, vLen, K，若 k != K，则哈希碰撞
9. 追加值到 dst

删除流程

1. Del(k []byte) 得到键
2. 计算 hash = xxhash3(k)
3. 计算 bucket 编号 bktIdx = hash%512，对 bucket[bktIdx] 进行操作
4. 获取 bucket 写入锁
5. 检查 hash 是否在 map 中，若否则 nop
6. 若记录 idx 所在 chunk 已分配，chunk.useCount--，若归零则将 chunk 放回 chunkPool
7. 从 map 中删除 hash 对应的记录

迭代器流程

1. Cache 迭代器桥接 512 个 bucket 迭代器
2. Bucket 迭代器创建时复制 map[hash]idx，每次 GetNext(kDst, vDst []byte) 获取读取锁，检验 idx isValid 并检验 hash 是否相符，若满足则追加 KV，否则跳过该记录使用下一条记录，直到没有更多记录

要困死了 🫠

和 cache lab 搏斗一天了，还是做不到满分吗？力竭了 🫠

终于成了 😋

报告

之前 64x64 一直不满，是因为 tiled8sb4 写入 4x4 块的顺序不是最优，导致多了 400 多个 miss

（左：tiled8sb4rev2，右：tiled8sb4）

最近突然发现我的Firefox浏览器上，AVIF也可以Progrssive rendering了😮，是我的错觉吗？

似乎是 bug，这张图实际上是 png，只是 URL 后缀为 .avif 😇

avif 似乎有某种 experimental progressive rendering 叫 layered

The AV1 Image File Format also supports multi-layer images as specified in [AV1] to be stored both in image items and image sequences. The AV1 Image File Format supports progressive image decoding through layered images.

This creates two layers, one at 1/8th resolution and 'minimum' quality, and one at full resolution and good quality. These layers work similarly to frames of a video, with the second layer using data from the first to save space (a P-frame in video terms).

似乎表现为先渲染低分辨率的 layer，目前 Firefox 未支持

有没有门友做过 malloclab，你们是如何测得 AVG_LIBC_THRUPUT 的？

我用 libc malloc 实现要求的接口并执行 mdriver 得到的值（41800 Kops/s）比给出的参考值（400 Kops/s）大得多，自己的 malloc 实现在 AVG_LIBC_THRUPUT=41800e3 下效率分只有 1/100 🥹

是因为我的实现太垃圾还是 AVG_LIBC_THRUPUT 的评估有问题 🤔

好消息：我是傻逼，文档里写了 mdriver -l 即可评估 libc malloc
坏消息：我是傻逼，mdriver -l 测得的 AVG_LIBC_THRUPUT 高达 48000e3 🤡

还有暗广

$ ./mdriver-rbt -lv
Team Name:ateam
Member 1 :Harry Bovik:[email protected]
Using default tracefiles in traces/
Measuring performance with gettimeofday().

Results for libc malloc:
trace  valid  util     ops      secs  Kops
 0       yes    0%    5694  0.000172 33162
 1       yes    0%    5848  0.000126 46376
 2       yes    0%    6648  0.000358 18549
 3       yes    0%    5380  0.000379 14188
 4       yes    0%   14400  0.000201 71820
 5       yes    0%    4800  0.000327 14688
 6       yes    0%    4800  0.000257 18699
 7       yes    0%   12000  0.000134 89686
 8       yes    0%   24000  0.000272 88235
 9       yes    0%   14401  0.000373 38598
10       yes    0%   14401  0.000082175622
Total           0%  112372  0.002680 41925

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   99%    5694  0.000131 43599
 1       yes  100%    5848  0.000142 41270
 2       yes   99%    6648  0.000161 41395
 3       yes  100%    5380  0.000130 41480
 4       yes   99%   14400  0.000113127321
 5       yes   96%    4800  0.000328 14625
 6       yes   95%    4800  0.000322 14930
 7       yes   55%   12000  0.000199 60211
 8       yes   50%   24000  0.000487 49271
 9       yes   68%   14401  0.000170 84563
10       yes   76%   14401  0.000086168236
Total          85%  112372  0.002268 49553

Perf index = 51 (util) + 40 (thru) = 91/100

这个方法感觉到头了 🫠

$ make && ./mdriver-rbt -v
make: Nothing to be done for 'all'.
Team Name:ateam
Member 1 :Harry Bovik:[email protected]
Using default tracefiles in traces/
Measuring performance with gettimeofday().

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   99%    5694  0.000140 40642
 1       yes   99%    5848  0.000149 39354
 2       yes   99%    6648  0.000166 39976
 3       yes  100%    5380  0.000122 43990
 4       yes   99%   14400  0.000107134705
 5       yes   96%    4800  0.000323 14874
 6       yes   95%    4800  0.000326 14724
 7       yes   96%   12000  0.000231 51903
 8       yes   85%   24000  0.000497 48261
 9       yes   80%   14401  0.000119121119
10       yes   89%   14401  0.000092155686
Total          94%  112372  0.002273 49442

Perf index = 57 (util) + 40 (thru) = 97/100

本来还想拿 PKU ICS 的 malloclab traces 测一下，结果发现 PKU 的 driver 是 64 位的
本来第一遍我就按照 64 位写的结果最后才看到 Makefile 里写的 -m32，真是草了

这里当时使用 LIFO free list + 每 n 次请求后统计 size 区间众数和 95% size，得到 default_size 和 max_size，然后限制 coalescing 至 max_size 以及 大于 default_size 才 split，但是事实证明完全没用

由于每次统计都需要 qsort 20 个 call bucket，同时 n 太小，导致效率极低（如果 n 太大则在有限的 trace 内无法触发统计），最终也无法知道这种方式在长期运行下是否有意义 🤔

话说这个算法还是学习自 github.com/valyala/bytebufferpool

具体是这里

mm_rbt

使用红黑树 free list 实现的 malloc

block

除全局数据以外，所有的堆内存都由 block 构成

block 的结构：

struct size_header {
    uint32_t psize;
    uint32_t csize;
};

struct block_header {
    struct size_header size;
    uint32_t color;
    union {
        struct {
            union {
                struct {
                    struct block_header* left;
                    struct block_header* right;
                };
                struct block_header* child[2];
            };
            struct block_header* parent;
        };
        struct {
            struct block_header* root;
            struct block_header* max;
            struct block_header* min;
        };
    };
};

size_header

size_header 记录上一个 block（在堆上）和当前 block 的大小和是否 free
uint32_t size_header::psize 和 uint32_t size_header::csize:

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|F|                     block_size (31 bits)                    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

• F: 块是否空闲
• block_size: 块的有效空间

由于 size_header 内有上一 block 的大小/空闲信息，堆顶必须维护一个 stub size_header 记录最后一个 block 的信息，以方便新 block 的创建

block_header

当 block 空闲时，block_header 的全部内容有效（否则只有 size_header 有效）
此时 block 为红黑树节点

当 block 为红黑树 header 节点时：

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                            psize                              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                            csize                              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                            color                              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                             root                              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                             max                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                             min                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

• root: 红黑树根节点，当树空时指向 sentinel 节点
• max/min: 指向最大/最小节点，用于 O(1) max/min 查询
• color: 节点颜色，此时恒为 black

当 block 为红黑树普通节点时：

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                            psize                              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                            csize                              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                            color                              |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                      left / child[0]                          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                      right / child[1]                         |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                            parent                             |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

• left / child[0]: 左子树
• right / child[1]: 右子树
• parent: 父节点

红黑树

参考 Red–black tree - Wikipedia

红黑树是一种自平衡二叉查找树

它的操作有着良好的最坏情况运行时间

mm_malloc

1. 查询红黑树，找到最合适的 free block，若未找到则进入 2.
   1.1 若 free_size - size >= block_header 大小，则拆分 free block 为此次分配的 block 和新的 free block 并放回红黑树
2. 若未找到，若 size <= 128 进入 3.，在堆上新建合适大小的 block 并返回
3. 小块预分配：扩展 size 到最近的 power of 2，并在此次分配的同时预分配 x(size) 个大小为 size 的 free block 加入到红黑树中（这样可以将类似的小块集中在一起，缓解小块带来的 external fragmentation）

查询红黑树可以先对比 O(1) max 节点的大小，如果 size 比这个还大就可以直接新建了

小块预分配让我的分数从 91 增长到 97，不过感觉有点面向测试设计了（

mm_free

1. 向更高地址查询空闲 block，直到遇到非空闲 block
2. 向低位地址查询空闲 block，直到遇到非空闲 block
3. 将所有查询到的空闲 block 从红黑树中删除，并合并为一个空闲 block 重新插入红黑树

这里其实可以限制最大合并大小，但是实际上没有这样做，也许可以进一步探索？（因为效率分满了所以好像没有意义）

mm_realloc

1. 若 size > block_size，进入 2.，若 block_size - size >= block_header 大小，则拆分原 block 为返回的 block 和新的 free block 并放回红黑树，返回原 block
2. 向高位地址统计空闲 block，若总空闲空间 < size 则回落至 malloc/copy/free，否则进入 3.
3. 若空闲空间 > size 则停止统计，将统计的空间 block 从红黑树中删除，合并为一个空闲 block
4. 若空闲 block 大小 - size > block_header 大小，则拆分空闲 block 为分配 block 和新的空闲 block 并放回红黑树
5. 返回原 block

C 好恶心啊我要写 Go

说实在的红黑树只是照着文档写出来的，要是自己独立实现恐怕还是做不到，实在是惭愧