V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
abersheeran
V2EX  ›  Python

优化了一波 Index.py 的 Radix Tree 实现

  •  
  •   abersheeran · 2020-09-05 00:09:20 +08:00 · 2842 次点击
    这是一个创建于 1552 天前的主题,其中的信息可能已经有所发展或是发生改变。

    https://github.com/abersheeran/index.py/blob/master/indexpy/routing/tree.py

    修了一个特定路由结构下会产生的 BUG (我写文档的时候靠脑子推算出来的,夸一波自己,我真牛逼),优化了一波代码结构,比之前那个我花了一夜糊出来的狗屎代码好多了。每次我有一个更屌的想法就感觉之前的东西都是狗屎哈哈哈。

    search 这一部分我从递归优化到了循环,但是 append 这一部分好像没什么从递归改循环的必要,毕竟 Index.py 的路由构建是在启动时,慢不到 0.01 秒应该没啥感觉。

    现在已经把路由构造、中间件展开和异步包装都全放到代码加载的时候去做了,运行的时候基本只有 search route 然后 parse params 最后 call handler 这样一个操作。

    这个地方还有没有优化的空间?这个版本的代码比之前那坨狗屎代码每 10000 次请求要慢 0.5 秒左右的样子,但是因为项目的路由多寡而导致的波动比之前要小,我也不知道啥情况,难道是因为之前没有匹配完全路由?还是因为这里用了栈的原因。希望 V2EX 有大佬愿意看看。

    性能测试在这 https://github.com/abersheeran/asgi-benchmark

    13 条回复    2020-09-09 12:06:55 +08:00
    fy
        1
    fy  
       2020-09-05 03:13:45 +08:00 via Android
    原来是 web 框架
    我在写的时候也想过 router 怎么弄,比如弄成一个大正则,根据匹配的 group 查 index 就知道是哪一个了。c 写的化简之后的 nfa 应该不慢吧?

    但是到了最后就偷懒了,我发现路由地址分两种,一种是确定的地址,占绝大多数。另一种是正则,占少量。那就为绝大多数做优化,由于确定的地址就是个 str,那么做个 dict 一查就行了,代价是 O(1),剩下正则就遍历。
    可能还有必要优化,不过我觉得思考 web 框架解决的问题比 router 更重要,暂时就不管了。

    看了 lz 的框架,真是同一个世界同一套技术栈,asgi uvicorn redoc aiofiles click pytest

    不同的地方是我对 pydantic 心存疑虑,我觉得报错信息太奇怪了,但是好像目前也没其他选择。

    此外我完全舍弃了模板的部分,因为我觉得 0202 年了,大家都前后端分离已经没人用模板了。框架没必要支持这个。

    还有就是感觉自己文档写的真心差,比不上 lz 写的(虽然内容也不多)完全没指望有开发者来用一样。

    这是我的 web 框架
    https://github.com/fy0/slim

    router 实现
    https://github.com/fy0/slim/blob/master/slim/base/route.py
    abersheeran
        2
    abersheeran  
    OP
       2020-09-05 14:15:43 +08:00
    @fy 你这个 DBView 思路很有意思啊。不过现在好像除了 restful,比较流行的就是 graphql,感觉你这个如果能增加自动生成数据库的 graphql 接口会有很有趣。graphql -> SQL 。

    路由的话,本来我之前是做的类似于 php 那个文件系统映射的,这个 Radix Tree 纯属是我和 starlette 谈崩了的产物。然后发现如果我先实现 Radix Tree,再实现我朋友给我提的 pr,也就是带路径参数的文件路由会比较简单。虽然这个文件路由跳票很久了……我个人感觉 web 框架要解决的最重要的问题其实就是路由,其他的反而好解决。因为可以让用户自己写。而路由系统是灵魂,由它来把请求和中间件、视图函数连接起来。这一部分做好了,其他部分就是堆代码优化用户体验的事了。而且目前 Python web 框架之间的路由寻找的差距会很明显……你看我的 benchmark 。不像 golang,一水的前缀树,速度完全是比拼其他部分了
    fy
        3
    fy  
       2020-09-05 15:03:39 +08:00
    @abersheeran #2

    我觉得 API 应该和数据更近,把 CRUD 的工作自动做掉。建立这个项目的时候,当时已经有 graphql 了,但一直觉得 graphql 思路很正确,但是不接地气,个人 /小团队来说有学习成本,大公司又有自己的一套体系同样用不上。

    应该有一种和传统接口形式类似的,易于使用的 API 框架。不过实践中用了几年也发现了挺多问题,所以包括权限、验证、SQLView 我都打算重新设计并重做了。
    总之做一个很大的 break change.

    架构设计的任务过重,细节的性能优化就只能先放一放了,反正 ASGI 的思必得够快。先把 feature 做好,fastapi 这种缝合怪也做的风生水起不是吗?
    fy
        4
    fy  
       2020-09-05 15:11:02 +08:00
    其实单从性能优化角度上讲,你还可以上 cython 然后打编译后的 wheel 传上 pypi,不过你用的打包工具是 poetry,好像是不支持二进制 wheel 包。
    abersheeran
        5
    abersheeran  
    OP
       2020-09-05 15:42:26 +08:00
    @fy Index.py 的设计上是只考虑纯 Python 的,所以暂时不会考虑这一类优化。不过如果特定用户有需求,可以通过替换 `app.router.http_tree` 属性来做。Index.py 里大部分地方都是这样可以替换的设计。
    fy
        6
    fy  
       2020-09-05 17:36:15 +08:00
    感觉我们做的工作互补性还挺强的,有没有兴趣后面一块搞点事情(比如共用的基础设施,表单验证、ORM 、权限机制等等)?
    abersheeran
        7
    abersheeran  
    OP
       2020-09-05 18:54:51 +08:00
    @fy 行啊。
    Harlaus
        8
    Harlaus  
       2020-09-05 21:40:08 +08:00
    框架的名字起得不太好
    fy
        9
    fy  
       2020-09-06 01:19:50 +08:00 via Android
    写了一封邮件给你
    abersheeran
        10
    abersheeran  
    OP
       2020-09-06 01:23:46 +08:00
    @fy 巧了。。我也发了一封邮件给你的 GitHub 上写的邮箱。已经回你发给我的那封了。
    fy
        11
    fy  
       2020-09-06 01:47:46 +08:00 via Android
    @abersheeran 原来是进垃圾箱了,捂脸。发了申请先睡觉了。
    haoliang
        12
    haoliang  
       2020-09-09 11:07:58 +08:00
    既然起因只是对 starlette 的路由实现有更好的想法,为啥 index.py 的定位不是一个单纯提供路由的库,而是 web 框架?

    这样想尝试你路由实现的人,就只能在 index.py 跟 starlette 之间做选择
    abersheeran
        13
    abersheeran  
    OP
       2020-09-09 12:06:55 +08:00
    @haoliang flask 的起因是因为和 bottle 有分歧,照你的意思 flask 就应该做一个纯粹的 WSGI 工具包咯?

    你不一定写过这种微型 web 框架,那我把之前解释过的问题再解释一遍:路由系统是一个微型 web 框架最重要的支柱,它负责分配路由、调用中间件、解析路径参数种种支柱功能,一个微型 web 框架的灵魂就只在于路由系统。如果把 starlette 的路由替换成前缀树,那其实就是另一个 index.py ,没差别。

    Index.py 的 request 和 response 对象都保持了 starlette 优秀的设计,你不妨试试。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1019 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 21:11 · PVG 05:11 · LAX 13:11 · JFK 16:11
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.