Allow path params with conflicting names and different methods

[dmitrybarsukov]

Closes issues #2201 and #1726

What was done:

1. Each node is now splitted into per-method handler with it's own ppath and pnames
2. Test case from #1726 at router_test.go

[codecov[bot]]

Codecov Report

Merging #2207 (459e309) into master (0644cd6) will decrease coverage by 0.14%. The diff coverage is 100.00%.

:exclamation: Current head 459e309 differs from pull request most recent head 69b71d0. Consider uploading reports for the commit 69b71d0 to get more accurate results

@@            Coverage Diff             @@
##           master    #2207      +/-   ##
==========================================
- Coverage   92.26%   92.11%   -0.15%     
==========================================
  Files          37       37              
  Lines        3090     3019      -71     
==========================================
- Hits         2851     2781      -70     
+ Misses        150      147       -3     
- Partials       89       91       +2     

Impacted Files	Coverage Δ
router.go	95.95% <100.00%> (-0.55%)	:arrow_down:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 0644cd6...69b71d0. Read the comment docs.

[ortyomka]

Sorry, but you copy my solution from #2208. I think, it's not good.

Proof (force-push): https://github.com/labstack/echo/compare/81ceb2f7e4a38689693dadf79c5ce4c5ca2f46b4..459e309d2067f032d0984f05d718ad4b13b90b8c

[aldas]

I'll check it soon but there seems to be little bit too few tests for huge change like that.

I see 3 things here:

1. performance: route is searched by method - thus more uncommon method types are routed faster as trees are smaller
2. functionality: we (could) support any method type instead of v4 fixed set. note: in v5 branch we have similar feature added but instead of adding all method I used additional map with current methof fields.
3. user experience: each route has their own instance of path parameter names. note: in v5 branch we have similar feature added.
5. I'm little but suspicious if this solution is not a little bit too naive. Having tree for each method and making sure that correct allowheader is composed is possibly a lot more complex due now having to find matching methods from multiple trees and what implications this has too OPTIONS performance

[aldas]

but this is cool PR as splitting single tree into tree for each method is thing that I have thought about trying out. Note: allow header can be sent for OPTIONS method and also for 405 (method not found) - I do not remember how good our tests cover all those things.

Note: similar stuff in v5 can be in this branch https://github.com/labstack/echo/tree/v5_alpha

[dmitrybarsukov]

@ortyomka hello! Yes, i've force-pushed new solution because my previous solution (separate trees for each method) had performance issues and much more allocs/op than original router. But it's not copy of your solution.

[aldas]

@dmitrybarsukov and @ortyomka have you though of splitting these changes into multiple PRs. I do not think that changing method tree structure should be in same change as where from path parameters are taken at the end of routing.

[dmitrybarsukov]

@aldas Sorry, my solution has serious performance issues.

Original benchmark

BenchmarkEchoStaticRoutes
BenchmarkEchoStaticRoutes-8                    	  113509	     10525 ns/op	       0 B/op	       0 allocs/op
BenchmarkEchoStaticRoutesMisses
BenchmarkEchoStaticRoutesMisses-8              	  113067	     10611 ns/op	       0 B/op	       0 allocs/op
BenchmarkEchoGitHubAPI
BenchmarkEchoGitHubAPI-8                       	   56080	     21848 ns/op	       0 B/op	       0 allocs/op
BenchmarkEchoGitHubAPIMisses
BenchmarkEchoGitHubAPIMisses-8                 	   57042	     21749 ns/op	       0 B/op	       0 allocs/op
BenchmarkEchoParseAPI
BenchmarkEchoParseAPI-8                        	  913242	      1270 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouterStaticRoutes
BenchmarkRouterStaticRoutes-8                  	  149326	      8167 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouterStaticRoutesMisses
BenchmarkRouterStaticRoutesMisses-8            	 3681016	       300.9 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouterGitHubAPI
BenchmarkRouterGitHubAPI-8                     	   75144	     15802 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouterGitHubAPIMisses
BenchmarkRouterGitHubAPIMisses-8               	 3314385	       361.7 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouterParseAPI
BenchmarkRouterParseAPI-8                      	 1495852	       795.7 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouterParseAPIMisses
BenchmarkRouterParseAPIMisses-8                	 6146856	       193.5 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouterGooglePlusAPI
BenchmarkRouterGooglePlusAPI-8                 	 2260587	       531.5 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouterGooglePlusAPIMisses
BenchmarkRouterGooglePlusAPIMisses-8           	 4245891	       282.5 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouterParamsAndAnyAPI
BenchmarkRouterParamsAndAnyAPI-8               	  901524	      1293 ns/op	       0 B/op	       0 allocs/op

map of method to tree solution

BenchmarkEchoStaticRoutes
BenchmarkEchoStaticRoutes-8                    	  102147	     11708 ns/op	       0 B/op	       0 allocs/op
BenchmarkEchoStaticRoutesMisses
BenchmarkEchoStaticRoutesMisses-8              	  102079	     11731 ns/op	       0 B/op	       0 allocs/op
BenchmarkEchoGitHubAPI
BenchmarkEchoGitHubAPI-8                       	   39241	     30526 ns/op	   15108 B/op	     236 allocs/op
BenchmarkEchoGitHubAPIMisses
BenchmarkEchoGitHubAPIMisses-8                 	   38858	     30129 ns/op	   15108 B/op	     236 allocs/op
BenchmarkEchoParseAPI
BenchmarkEchoParseAPI-8                        	  509515	      2271 ns/op	     832 B/op	      26 allocs/op
BenchmarkRouterStaticRoutes
BenchmarkRouterStaticRoutes-8                  	  125223	      9895 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouterStaticRoutesMisses
BenchmarkRouterStaticRoutesMisses-8            	 1000000	      1195 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouterGitHubAPI
BenchmarkRouterGitHubAPI-8                     	   45582	     26628 ns/op	   15108 B/op	     236 allocs/op
BenchmarkRouterGitHubAPIMisses
BenchmarkRouterGitHubAPIMisses-8               	  381775	      3166 ns/op	    1024 B/op	      16 allocs/op
BenchmarkRouterParseAPI
BenchmarkRouterParseAPI-8                      	  603487	      2012 ns/op	     832 B/op	      26 allocs/op
BenchmarkRouterParseAPIMisses
BenchmarkRouterParseAPIMisses-8                	  555308	      2163 ns/op	     512 B/op	      16 allocs/op
BenchmarkRouterGooglePlusAPI
BenchmarkRouterGooglePlusAPI-8                 	 1000000	      1067 ns/op	     416 B/op	      13 allocs/op
BenchmarkRouterGooglePlusAPIMisses
BenchmarkRouterGooglePlusAPIMisses-8           	  565418	      2119 ns/op	     512 B/op	      16 allocs/op
BenchmarkRouterParamsAndAnyAPI
BenchmarkRouterParamsAndAnyAPI-8               	  476144	      2556 ns/op	    1920 B/op	      24 allocs/op

As you see, it has much more ns/op and >0 allocs/op. So, i had to rewrite router logic and make map of method to handler inside each node. This variant gives much better results.

map in each node solution

BenchmarkEchoStaticRoutes
BenchmarkEchoStaticRoutes-8                    	   93038	     13065 ns/op	       0 B/op	       0 allocs/op
BenchmarkEchoStaticRoutesMisses
BenchmarkEchoStaticRoutesMisses-8              	   91372	     13125 ns/op	       0 B/op	       0 allocs/op
BenchmarkEchoGitHubAPI
BenchmarkEchoGitHubAPI-8                       	   47766	     26254 ns/op	       0 B/op	       0 allocs/op
BenchmarkEchoGitHubAPIMisses
BenchmarkEchoGitHubAPIMisses-8                 	   47211	     25293 ns/op	       0 B/op	       0 allocs/op
BenchmarkEchoParseAPI
BenchmarkEchoParseAPI-8                        	  673542	      1790 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouterStaticRoutes
BenchmarkRouterStaticRoutes-8                  	  105259	     11410 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouterStaticRoutesMisses
BenchmarkRouterStaticRoutesMisses-8            	 3792248	       312.0 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouterGitHubAPI
BenchmarkRouterGitHubAPI-8                     	   56343	     21262 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouterGitHubAPIMisses
BenchmarkRouterGitHubAPIMisses-8               	 3242745	       370.4 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouterParseAPI
BenchmarkRouterParseAPI-8                      	  907677	      1313 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouterParseAPIMisses
BenchmarkRouterParseAPIMisses-8                	 5698016	       211.0 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouterGooglePlusAPI
BenchmarkRouterGooglePlusAPI-8                 	 1675465	       716.5 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouterGooglePlusAPIMisses
BenchmarkRouterGooglePlusAPIMisses-8           	 3999283	       302.2 ns/op	       0 B/op	       0 allocs/op
BenchmarkRouterParamsAndAnyAPI
BenchmarkRouterParamsAndAnyAPI-8               	  578578	      2063 ns/op	       0 B/op	       0 allocs/op

Can you please re-review my PR again?

[ortyomka]

@dmitrybarsukov I can doubt since my solution appeared 30 minutes later than your original one, and then after another 30 minutes your solution changes to a very similar one to mine. (similar checks, names)

[ortyomka]

@aldas I will split my PR

[aldas]

Note: support for different params names for same path is probably going to get merged way faster than tree changes. I engourage you to use benchstat to compare different solutions. See how we did for last huge change to router https://github.com/labstack/echo/pull/1770#issuecomment-778435253 here.

[dmitrybarsukov]

@aldas Here is benchstat output for related benchmarks. I added arrow "<---" to benches which were critially affected

name \ time/op                          original.txt  first_solution.txt  second_solution.txt
EchoStaticRoutes-8                       10.6µs ± 0%         12.0µs ± 0%          13.1µs ± 0%
EchoStaticRoutesMisses-8                 10.6µs ± 0%         11.9µs ± 0%          12.9µs ± 0%
EchoGitHubAPI-8                          20.8µs ± 0%         31.8µs ± 0%          25.8µs ± 0%
EchoGitHubAPIMisses-8                    20.7µs ± 0%         30.9µs ± 0%          25.0µs ± 0%
EchoParseAPI-8                           1.22µs ± 0%         2.30µs ± 0%          1.78µs ± 0%   <---
RouterStaticRoutes-8                     8.04µs ± 0%         9.74µs ± 0%         11.19µs ± 0%
RouterStaticRoutesMisses-8                297ns ± 0%         1175ns ± 0%           309ns ± 0%   <---
RouterGitHubAPI-8                        15.8µs ± 0%         26.9µs ± 0%          21.1µs ± 0%
RouterGitHubAPIMisses-8                   361ns ± 0%         3169ns ± 0%           368ns ± 0%   <---
RouterParseAPI-8                          796ns ± 0%         1996ns ± 0%          1308ns ± 0%   <---
RouterParseAPIMisses-8                    194ns ± 0%         2226ns ± 0%           210ns ± 0%   <---
RouterGooglePlusAPI-8                     531ns ± 0%         1086ns ± 0%           713ns ± 0%   <---
RouterGooglePlusAPIMisses-8               287ns ± 0%         2046ns ± 0%           304ns ± 0%   <---
RouterParamsAndAnyAPI-8                  1.31µs ± 0%         2.56µs ± 0%          2.08µs ± 0%   <---

name \ alloc/op                         original.txt  first_solution.txt  second_solution.txt
EchoStaticRoutes-8                        0.00B               0.00B                0.00B
EchoStaticRoutesMisses-8                  0.00B               0.00B                0.00B
EchoGitHubAPI-8                           0.00B           15108.00B ± 0%           0.00B   <---
EchoGitHubAPIMisses-8                     0.00B           15108.00B ± 0%           0.00B   <---
EchoParseAPI-8                            0.00B             832.00B ± 0%           0.00B   <---
RouterStaticRoutes-8                      0.00B               0.00B                0.00B
RouterStaticRoutesMisses-8                0.00B               0.00B                0.00B
RouterGitHubAPI-8                         0.00B           15108.00B ± 0%           0.00B   <---
RouterGitHubAPIMisses-8                   0.00B            1024.00B ± 0%           0.00B   <---
RouterParseAPI-8                          0.00B             832.00B ± 0%           0.00B   <---
RouterParseAPIMisses-8                    0.00B             512.00B ± 0%           0.00B   <---
RouterGooglePlusAPI-8                     0.00B             416.00B ± 0%           0.00B   <---
RouterGooglePlusAPIMisses-8               0.00B             512.00B ± 0%           0.00B   <---
RouterParamsAndAnyAPI-8                   0.00B            1920.00B ± 0%           0.00B   <---

name \ allocs/op                        original.txt  first_solution.txt  second_solution.txt
EchoStaticRoutes-8                         0.00                0.00                 0.00
EchoStaticRoutesMisses-8                   0.00                0.00                 0.00
EchoGitHubAPI-8                            0.00              236.00 ± 0%            0.00   <---
EchoGitHubAPIMisses-8                      0.00              236.00 ± 0%            0.00   <---
EchoParseAPI-8                             0.00               26.00 ± 0%            0.00   <---
RouterStaticRoutes-8                       0.00                0.00                 0.00
RouterStaticRoutesMisses-8                 0.00                0.00                 0.00
RouterGitHubAPI-8                          0.00              236.00 ± 0%            0.00   <---
RouterGitHubAPIMisses-8                    0.00               16.00 ± 0%            0.00   <---
RouterParseAPI-8                           0.00               26.00 ± 0%            0.00   <---
RouterParseAPIMisses-8                     0.00               16.00 ± 0%            0.00   <---
RouterGooglePlusAPI-8                      0.00               13.00 ± 0%            0.00   <---
RouterGooglePlusAPIMisses-8                0.00               16.00 ± 0%            0.00   <---
RouterParamsAndAnyAPI-8                    0.00               24.00 ± 0%            0.00   <---

[dmitrybarsukov]

@aldas

have you though of splitting these changes into multiple PRs

Did you mean to create different PR's for my first solution (separate tree for each method) and second solution (where each node has map of method to handler with its own ppath and pnames) ?