[GitHub] [incubator-nuttx] a-lunev commented on a change in pull request #4433: net/devif/devif_callback.c: corrected the connection event list to work as FIFO instead of LIFO

[GitBox <gi...@apache.org>]

a-lunev commented on a change in pull request #4433:
URL: https://github.com/apache/incubator-nuttx/pull/4433#discussion_r703066321



##########
File path: net/devif/devif.h
##########
@@ -260,6 +260,9 @@ typedef CODE uint16_t (*devif_callback_event_t)(FAR struct net_driver_s *dev,
 struct devif_callback_s
 {
   FAR struct devif_callback_s *nxtconn;
+  FAR struct devif_callback_s *tail_helper; /* The tail helper field is used

Review comment:
       Hi Xiang,
   Initially (for simplicity) just to check if FIFO vs LIFO helps to resolve the root issue, I applied a loop to find the tail in the list (I did not commit that code). As I made sure it resolved the issue, I improved the code and eliminated the loop by adding the tail helper. Thus you can see my current PR is w/o the loop.
   The list is normally short only during low network traffic. During high network traffic the list grows towards to the maximum length, thus it is normally long instead.
   Considering the process of adding items to the list, the time complexity was O(n) in LIFO mode.
   If the loop is applied to find the list tail each time when a new item is added to the list, then the time complexity becomes near to O(n^2).
   As I avoided applying the loop, the time complexity still stays O(n) as it was before my change.
   Thus I think it's not good to make it O(n^2) to degrade the total performance (it's especially important in case of high network traffic).




-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@nuttx.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org