如何将数据存储在控制流中

2023年 7月 26日 42.4k 0

​在设计并发程序时,一个经常出现的决策是将程序状态表示为控制流还是数据。本文将讨论这个决策的含义以及如何处理它。如果处理得当,将存储在数据中的程序状态改为存储在控制流中,可以使程序比原本更清晰、更易维护。

在深入探讨之前,重要的是要注意并发和并行不是一回事:

  • 并发是关于编写程序的方式,关于能够独立执行控制流(无论你将它们称为进程、线程、协程、goroutine等),使得你的程序可以同时处理多个任务而不会变成一团糟。
  • 另一方面,并行是关于执行程序的方式,允许多个计算同时运行,以使得你的程序可以高效地同时执行多个任务。

并发天然适合于并行执行,但本文关注的重点是如何利用并发编写更清晰的程序,而不是更快的程序。

并发程序和非并发程序的区别在于,并发程序可以被编写得好像它们在同时执行多个独立的控制流。这些较小的控制流的名称因语言而异:线程、任务、进程、纤程、协程、goroutine等等。不管名称如何,本文的基本观点是,以多个独立执行的控制流形式编写程序,允许你将程序状态存储在其中一个或多个控制流的执行状态中,具体来说是存储在程序计数器(正在执行的行号)和堆栈中。当然,控制流状态始终可以作为显式数据来维护,但这样显式的数据形式实际上是在模拟控制流。大多数情况下,使用编程语言内置的控制流特性比在数据结构中模拟它们更易于理解、推理和维护。

本文的其余部分将通过一些具体示例来说明我之前提到的将数据存储在控制流中的抽象概念。这些示例恰好是用Go语言编写的,但这些思想适用于任何支持编写并发程序的语言,包括几乎所有现代语言。

分步示例

下面是一个看似微不足道的问题,它展示了将程序状态存储在控制流中的意义。假设我们正在从文件中读取字符,并希望扫描C风格的双引号字符串。在这种情况下,我们有一个非并行的程序。这里没有并行的机会,但正如我们将看到的,并发仍然可以发挥有用的作用。如果我们不关心字符串中的精确转义序列,只需匹配正则表达式"([^"]|.)*"即可,它匹配一个双引号,然后是零个或多个字符,最后是另一个双引号。在引号之间,一个字符可以是任何不是引号或反斜杠的字符,或者是一个反斜杠后面跟着任何字符(包括引号或反斜杠)。每个正则表达式都可以编译成有限自动机或状态机,所以我们可以使用一个工具将这个规范转换成以下Go代码:

state := 0
for {
    c := read()
    switch state {
    case 0:
        if c != '"' {
            return false
        }
        state = 1
    case 1:
        if c == '"' {
            return true
        }
        if c == '\\' {
            state = 2
        } else {
            state = 1
        }
    case 2:
        state = 1
    }
}

代码中有一个名为state的变量,表示自动机的状态。for循环读取一个字符并更新状态,不断循环,直到找到字符串的末尾或语法错误。这是一种只有程序才能喜欢的代码。对于人来说很难理解,维护起来也很困难。
这个程序如此晦涩的主要原因是它的程序状态存储为数据,具体来说是存储在名为state的变量中。当可以将状态存储在代码中时,通常会得到一个更清晰的程序。为了看到这一点,让我们逐步将程序转换为等价但更易理解的版本。我们可以从将读取调用复制到switch的每个case中开始:

state := 0                          state := 0
for {                               for {
    c := read()                     
    switch state {                      switch state {
    case 0:                             case 0:
                                            c := read()
        if c != '"' {                       if c != '"' {
            return false                        return false
        }                                   }
        state = 1                           state = 1
    case 1:                             case 1:
                                            c := read()
        if c == '"' {                       if c == '"' {
            return true                         return true
        }                                   }
        if c == '\\' {                      if c == '\\' {
            state = 2                           state = 2
        } else {                            } else {
            state = 1                           state = 1
        }                                   }
    case 2:                             case 2:
                                            c := read()
        state = 1                           state = 1
    }                                   }
}                                   }

(在下面和所有后续的显示中,旧程序在左边,新程序在右边,未更改的行以灰色文本打印。)
现在,我们可以使用代码标签和goto语句,而不是将结果写入state然后立即再次进入for循环以查找在该状态下要执行的操作:

state := 0                          state0:
for {                               
    switch state {                  
    case 0:                         
        c := read()                     c := read()
        if c != '"' {                   if c != '"' {
            return false                    return false
        }                               }
        state = 1                       goto state1
    case 1:                         state1:
        c := read()                     c := read()
        if c == '"' {                   if c == '"' {
            return true                     return true
        }                               }
        if c == '\\' {                  if c == '\\' {
            state = 2                       goto state2
        } else {                        } else {
            state = 1                       goto state1
        }                               }
    case 2:                         state2:
        c := read()                     read()
        state = 1                       goto state1
    }                               
}

然后我们可以进一步简化程序。位于 state1 标签之前的 goto state1 是一个无操作指令,可以删除。而且我们可以看到只有一种方式可以到达 state2,因此我们可以将 goto state2 替换为 state2 中的实际代码:

state0:                         state0:
    c := read()                     c := read()
    if c != '"' {                   if c != '"' {
        return false                    return false
    }                               }
    goto state1                 
state1:                         state1:
    c := read()                     c := read()
    if c == '"' {                   if c == '"' {
        return true                     return true
    }                               }
    if c == '\\' {                  if c == '\\' {
        goto state2             
    } else {                    
        goto state1             
    }                           
state2:                         
    read()                              read()
    goto state1                         goto state1
                                    } else {
                                        goto state1
                                    }

然后我们可以将 if 语句的两个分支中的 "goto state1" 提取出来。

state0:                         state0:
    c := read()                     c := read()
    if c != '"' {                   if c != '"' {
        return false                    return false
    }                               }
​
state1:                         state1:
    c := read()                     c := read()
    if c == '"' {                   if c == '"' {
        return true                     return true
    }                               }
    if c == '\\' {                  if c == '\\' {
        read()                          read()
        goto state1                 }
    } else {                        goto state1
        goto state1             
    }

然后我们可以删除未使用的 state0 标签,并用一个真正的循环替换 state1 的循环。现在我们有了一个看起来像真正的程序的东西:

state0:                         
    c := read()                 c := read()
    if c != '"' {               if c != '"' {
        return false                return false
    }                           }
​
state1:                         for {
    c := read()                     c := read()
    if c == '"' {                   if c == '"' {
        return true                     return true
    }                               }
    if c == '\\' {                  if c == '\\' {
        read()                          read()
    }                               }
    goto state1                 }

我们可以进一步简化,消除一些不必要的变量,并将对最后一个引号 (c == "") 的检查作为循环终止条件。

c := read()                     if read() != '"' {
if c != '"' {                   
    return false                    return false
}                               }
​
for {                           var c byte
    c := read()                 for c != '"' {
    if c == '"' {                   c = read()
        return true             
    }                           
    if c == '\\' {                  if c == '\\' {
        read()                          read()
    }                               }
}                               }
                                return true

最终版本如下:

func parseQuoted(read func() byte) bool {
    if read() != '"' {
        return false
    }
    var c byte
    for c != '"' {
        c = read()
        if c == '\\' {
            read()
        }
    }
    return true
}

之前我解释了正则表达式,说它“匹配一个双引号,然后是零个或多个字符的序列,然后是另一个双引号。在引号之间,一个字符可以是除了引号或反斜杠之外的任何字符,或者是一个反斜杠后面跟着任何字符。”很容易看出,这个程序恰好做到了这一点。手写程序也可以利用控制流。例如,这是一个人可能手写的版本:

if read() != '"' {
    return false
}
inEscape := false
for {
    c := read()
    if inEscape {
        inEscape = false
        continue
    }
    if c == '"' {
        return true
    }
    if c == '\\' {
        inEscape = true
    }
}

可以使用相同的小步骤将变量 inEscape 的数据表示方式转换为控制流,最终得到相同的简化版本。
无论哪种方式,原始程序中的状态变量现在隐式地由程序计数器表示,即表示程序的哪个部分正在执行。这个版本中的注释指示了原始状态变量(或 inEscape)的隐式值:

func parseQuoted(read func() byte) bool {
    // state == 0
    if read() != '"' {
        return false
    }
​
    var c byte
    for c != '"' {
        // state == 1 (inEscape = false)
        c = read()
        if c == '\\' {
            // state == 2 (inEscape = true)
            read()
        }
    }
    return true
}

原始程序本质上是使用显式的状态变量作为程序计数器来模拟这个控制流,跟踪正在执行的代码行。如果一个程序可以转换为将显式状态存储在控制流中,那么显式状态只是对控制流的笨拙模拟。

更多线程更多状态

在广泛支持并发性之前,这种笨拙的模拟通常是必要的,因为程序的不同部分希望使用控制流。例如,假设要解析的文本是对base64输入进行解码的结果,在该解码器中,每个由64个字符组成的6位字符序列解码为3个8位字节。解码器的核心如下所示:

for {
    c1, c2, c3, c4 := read(), read(), read(), read()
    b1, b2, b3 := decode(c1, c2, c3, c4)
    write(b1)
    write(b2)
    write(b3)
}

如果我们希望这些写入调用传递给上一节中的解析器,我们需要一个可以逐字节调用的解析器,而不是一个要求读回调的解析器。这个解码循环不能被呈现为一个读回调,因为它一次获取3个输入字节,并使用其控制流来跟踪已写入的字节。因为解码器在其控制流中存储了自己的状态,所以parseQuoted无法这样做。
在一个非并发程序中,这个base64解码器和parseQuoted会陷入僵局:一个必须放弃对控制流状态的使用,并退回到某种模拟版本中。为了重写parseQuoted,我们必须重新引入状态变量,可以将其封装在一个带有Write方法的结构体中:

type parser struct {
    state int
}
​
func (p *parser) Init() {
    p.state = 0
}
​
func (p *parser) Write(c byte) Status {
    switch p.state {
    case 0:
        if c != '"' {
            return BadInput
        }
        p.state = 1
    case 1:
        if c == '"' {
            return Success
        }
        if c == '\\' {
            p.state = 2
        } else {
            p.state = 1
        }
    case 2:
        p.state = 1
    }
    return NeedMoreInput
}

Init方法初始化状态,然后每个Write方法加载状态,在状态和输入字节的基础上执行相应的操作,然后将状态保存回结构体中。
对于parseQuoted函数来说,状态机足够简单,这种方式可能完全可以。但是,如果状态机更加复杂,或者算法最好以递归方式表达,那么按照调用者以每次一个字节的方式传递输入序列意味着将所有这些状态明确地放在一个模拟原始控制流的数据结构中。并发消除了程序中不同部分之间关于哪个部分可以在控制流中存储状态的争用,因为现在可以有多个控制流。假设我们已经有了parseQuoted函数,它庞大而复杂,经过了测试且正确无误,我们不想对其进行任何更改。我们可以通过编写以下包装器来避免对该代码进行任何编辑:

type parser struct {
c chan byte
status chan Status
}

func (p *parser) Init() {
p.char = make(chan byte)
p.status = make(chan Status)
go p.run()

相关文章

JavaScript2024新功能:Object.groupBy、正则表达式v标志
PHP trim 函数对多字节字符的使用和限制
新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
为React 19做准备:WordPress 6.6用户指南
如何删除WordPress中的所有评论

发布评论