CS144 (2023 Spring) Lab 1: stitching substrings into a byte stream

Article directory

Preface
- Other notes
- Related Links
1. Getting started
2. Putting substrings in sequence
- 2.1 Requirements analysis
- 2.2 Things to note
- 2.3 Code implementation
3. Testing and Optimization

Foreword

This Lab mainly implements the string reception and reassembly part of a TCP receiver.

Other notes

Lab 0: networking warmup
Lab 1: stitching substrings into a byte stream

1. Getting started

The CS144 Lab originally reused code from top to bottom, which led me to kill the remote library at the beginning. Unexpectedly, the Lab actually called me merge, so let’s do it again:

git remote add base [email protected]:CS144/minnow.git
git fetch base

Open the branch manager of VS, and you can see that check1 – 6 should be released one by one in the remote library. Looking at the submission record, this should be a warehouse that was created step by step during class. Theoretically speaking, you can directly merge the check6 branch. Got it

Right-click and merge into main, accept the conflict, then submit for upload, and you can continue coding.

2. Putting substrings in sequence

2.1 Requirements Analysis

What Lab1 and 2 do is to write a TCP receiver, which works roughly like what was written at the end of Lab0, writing a class to process the byte stream, but this data will not be transmitted in memory, but through the network.

Due to the uncertainty and cost of network transmission, when transmitting data, we cut the string into segments, such as each of the

short\ segments

short segments shall not exceed 1460

byte

byte, and considering the uncertainty of network transmission and the nature of TCP, these fields are usually out of order and lost, and we need to ensure that we can rearrange them back to the original string.

Specifically for this Lab, we want to implement a program called

Reassembler

Reassembler is used to accept the bunch of fields mentioned above at the receiving end, and each

Byte

Byte (instead of

segment

segment) has a corresponding

index

index. The document constrains two necessary interfaces of this class. insert writes a data into output, and the writing position is from first_index, it also uses a bool variable to identify whether the current segment is the last segment; while bytes_pending only returns the existence

Reassembler

Bytes in Reassembler, but which bytes exist here? We know that simple network transmission does not guarantee the order. It is possible to receive the following fields in advance, so we have to temporarily store them.

Reassembler

Reassembler, wait until the fields in front of it are written before saving it.

It then goes on to show some details of what this class should do.

First, we should know the next byte of the stream to be received (the

index

index), as mentioned above, there are still a lot of fields inside the class waiting to be fed and waiting to flow;

Then, we need to process the strings that arrive early and are not yet pushed into the stream;

Bytes that exceed the stream’s reception capacity should be discarded directly;

Then this picture demonstrates that there are three types of bytes: those that have not been temporarily stored in the stream, those that have been buffered in the stream, and those that have been ejected by read. Our Lab should not consider the third one. The green memory and the entire temporary space within the class together form capacity. It can be seen that the maximum value of our red memory can only be capacity - buffered. Anything exceeding this The knot has to be thrown away. In terms of implementation, this value is the available_capacity implemented by the previous Lab.

2.2 Notes

Then there are some FAQs where we can distill this information:

flowing
i

n

d

e

x

index

index starts from 0;
We will have the same benchmarking environment as Lab0;
Each field is an accurate slice from the string, no exception handling is required;
Encourage the use of standard libraries and data structures;
Push bytes into the stream as early as possible so as not to keep them forever;
The data string received by insert may overlap with other strings;
You can add private members to a class (isn’t this nonsense);
For each byte, only one copy of it should be stored inside the class, and no overlapping strings should be stored;
Run ./scripts/lines-of-code to calculate the number of lines of code implemented. This value is generally 50-60.

2.3 Code Implementation

My code implementation is given below. There are many comments in it, so I won’t go into details here. However, please note that I used std::ranges and std::views here. Therefore, your compiler must be gcc13.1 or above. What needs to be discussed a little bit is what data structure should be used as

buffer

buffer, what kind of requirements does this data structure need to meet? First, it will frequently insert anywhere, and then it needs to frequently traverse and compare sizes to find, giving the complexity of several common data structures:

	Insert	Head delete	Delete k	Find
list	O ( 1 ) O(1) O(1)	O ( 1 ) O(1) O(1)	O ( k ) O(k) O(k)	O ( n ) O(n) O(n)
vector	O ( n ) O(n) O(n)	O ( n ) O(n) O(n)	O ( n ) O(n) O(n)	O ( log ? n ) O(\log n) O(logn)
deque	O ( n ) O(n) O(n)	O ( 1 ) O(1) O(1)	O ( n ) O(n) O(n)	O ( log ? n ) O(\log n) O(logn)
map	O ( log ? n ) O(\log n) O(logn)	O ( log ? n ) O(\log n) O(logn)	O ( log ? n + k ) O(\log n + k) O(logn + k)	O ( n ) O(n) O(n)

Insert

Head delete

Delete k

Find

list

(

)

O(1)

(

)

O(1)

(

)

O(k)

(

)

O(n)

vector

(

)

O(n)

(

)

O(n)

(

)

O(n)

(

log

)

O(\log n)

O(logn)

deque

(

)

O(n)

(

)

O(1)

(

)

O(n)

(

log

)

O(\log n)

O(logn)

map

(

log

)

O(\log n)

O(logn)

(

log

)

O(\log n)

O(logn)

(

log

)

O(\log n + k)

O(logn + k)

(

)

O(n)

It can be seen that list is basically the best container when considered comprehensively. Among them, although the search that comes with map red-black tree is

(

log

)

O(\log n)

O(logn), but our search is to find two endpoints. If the pair of the left and right intervals is used as the key, then its built-in binary search algorithm cannot be used– It cannot pass custom comparison predicates, and if you use the binary algorithm in because its iterator does not meet the conditions of a random iterator, it means that you can only

(

)

O(n)

O(n) search. Taken together, it is optimal for us to maintain an ordered linked list.

In addition to

buffer

The process of buffer temporary storage may involve the problem of interval merging. You can refer to LeetCode 57. Inserting intervals.
, given my implementation of this question, this Lab can directly apply it:

// https://leetcode.cn/u/zi-bu-yu-mf/
class Solution {<!-- -->
public:
    vector<vector<int>> insert(vector<vector<int>> & amp; intervals, vector<int> & amp; newInterval) {<!-- -->
        auto beg = intervals.begin(), end = intervals.end();
        int & amp; a = newInterval[0], & amp; b = newInterval[1];
        auto l = lower_bound(beg, end, vector{<!-- --> a, a });
        auto r = upper_bound( l, end, vector{<!-- --> b, b});
        if (l != end) a = min(a, l[ 0][0]);
        if (r != beg) b = max(b, r[-1][1]);
        intervals.insert(intervals.erase(l, r), newInterval);
        return intervals;
    }
};

/********************************************** *********************//**
 * \file reassembler.hh
 * \brief implements a Reassembler class, which is used to reassemble disordered strings into ordered ones.
 * String and pushed into byte stream.
 *
 * \author JMC
 * \date August 2023
 *************************************************** *******************/
#pragma once

#include "byte_stream.hh"

#include <string>
#include <list>
#include <tuple>

classReassembler
{<!-- -->
bool had_last_ {<!-- -->}; // Whether the last string has been inserted
uint64_t next_index_ {<!-- -->}; // Index of the next byte to be written
uint64_t buffer_size_ {<!-- -->}; // Number of bytes in buffer_
std::list<std::tuple<uint64_t, uint64_t, std::string>> buffer_ {<!-- -->};

/**
* \breif pushes data into the output stream.
*/
void push_to_output(std::string data, Writer & amp; output);

/**
* \brief Push data into the buffer temporary area.
* \param first_index The index of the first byte of data
* \param last_index The index of the last byte of data
* \param data The string to be pushed, the subscript is [first_index, last_index] closed interval
*/
void buffer_push( uint64_t first_index, uint64_t last_index, std::string data );

/**
* Try to push the string in the buffer into the output stream.
*/
void buffer_pop(Writer & amp; output);

public:
  /*
   * Insert a new substring to be reassembled into a ByteStream.
   * `first_index`: the index of the first byte of the substring
   * `data`: the substring itself
   * `is_last_substring`: this substring represents the end of the stream
   * `output`: a mutable reference to the Writer
   *
   * The Reassembler's job is to reassemble the indexed substrings (possibly out-of-order
   * and possibly overlapping) back into the original ByteStream. As soon as the Reassembler
   * learns the next byte in the stream, it should write it to the output.
   *
   * If the Reassembler learns about bytes that fit within the stream's available capacity
   * but can't yet be written (because earlier bytes remain unknown), it should store them
   * internally until the gaps are filled in.
   *
   * The Reassembler should discard any bytes that lie beyond the stream's available capacity
   * (i.e., bytes that couldn't be written even if earlier gaps get filled in).
   *
   * The Reassembler should close the stream after writing the last byte.
   */
  void insert( uint64_t first_index, std::string data, bool is_last_substring, Writer & amp; output );

  // How many bytes are stored in the Reassembler itself?
  uint64_t bytes_pending() const;
};

/********************************************** *********************//**
 * \file reassembler.cc
 * \brief implements a Reassembler class, which is used to reassemble disordered strings into ordered ones.
 * String and pushed into byte stream.
 * \author JMC
 * \date August 2023
 *************************************************** *******************/
#include "reassembler.hh"

#include <ranges>
#include <algorithm>

using namespace std;
void Reassembler::push_to_output( std::string data, Writer & amp; output ) {<!-- -->
  next_index_ + = data.size();
  output.push( move( data ) );
}

void Reassembler::buffer_push( uint64_t first_index, uint64_t last_index, std::string data )
{<!-- -->
  // merge range
  auto l = first_index, r = last_index;
  auto beg = buffer_.begin(), end = buffer_.end();
  auto lef = lower_bound( beg, end, l, []( auto & amp; a, auto & amp; b ) {<!-- --> return get<1>( a ) < b; } );
  auto rig = upper_bound( lef, end, r, []( auto & amp; b, auto & amp; a ) {<!-- --> return get<0>( a ) > b; } );
  if (lef != end) l = min( l, get<0>( *lef ) );
  if (rig != beg) r = max( r, get<1>( *prev( rig ) ) );
  
  // When data is already in buffer_, return directly
  if ( lef != end & amp; & amp; get<0>( *lef ) == l & amp; & amp; get<1>( *lef ) == r ) {<!-- -->
    return;
  }

  buffer_size_ + = 1 + r - l;
  if ( data.size() == r - l + 1 & amp; & amp; lef == rig ) {<!-- --> // When there is no overlapping data in buffer_
buffer_.emplace( rig, l, r, move( data ) );
return;
  }
  string s( 1 + r - l, 0 );

  for ( auto & amp; & amp; it : views::iota( lef, rig ) ) {<!-- -->
auto & amp; [a, b, c] = *it;
buffer_size_ -= c.size();
    ranges::copy(c, s.begin() + a - l);
  }
  ranges::copy(data, s.begin() + first_index - l);
  buffer_.emplace( buffer_.erase( lef, rig ), l, r, move( s ) );
}

void Reassembler::buffer_pop( Writer & amp; output ) {<!-- -->
  while ( !buffer_.empty() & amp; & amp; get<0>( buffer_.front() ) == next_index_ ) {<!-- -->
    auto & amp; [a, b, c] = buffer_.front();
    buffer_size_ -= c.size();
    push_to_output( move( c ), output );
    buffer_.pop_front();
  }

  if ( had_last_ & amp; & amp; buffer_.empty() ) {<!-- -->
    output.close();
  }
}

void Reassembler::insert( uint64_t first_index, string data, bool is_last_substring, Writer & amp; output )
{<!-- -->
  if ( data.empty() ) {<!-- -->
    if ( is_last_substring ) {<!-- -->
      output.close();
    }
    return;
  }
  auto end_index = first_index + data.size(); // data: [first_index, end_index)
  auto last_index = next_index_ + output.available_capacity(); // Available range: [next_index_, last_index)
  if ( end_index < next_index_ || first_index >= last_index ) {<!-- -->
    return; // Not within the available range, return directly
  }

  //Adjust the range of data
  if ( last_index < end_index ) {<!-- -->
    end_index = last_index;
    data.resize( end_index - first_index );
    is_last_substring = false;
  }
  if ( first_index < next_index_ ) {<!-- -->
    data = data.substr( next_index_ - first_index );
    first_index = next_index_;
  }

  // If data can be written directly to the output, write it directly
  if ( first_index == next_index_ & amp; & amp; ( buffer_.empty() || end_index < get<1>( buffer_.front() ) + 2 ) ) {<!-- -->
    if ( buffer_.size() ) {<!-- --> // If there is overlap, adjust the range of data
      data.resize( min( end_index, get<0>( buffer_.front() ) ) - first_index );
    }
    push_to_output( move( data ), output );
  } else {<!-- --> // Otherwise, insert data into buffer_
    buffer_push( first_index, end_index - 1, data);
  }
  had_last_ |= is_last_substring;
  
  //Try to write the data in buffer_ to output
  buffer_pop(output);
}

uint64_t Reassembler::bytes_pending() const
{<!-- -->
  return buffer_size_;
}

3. Testing and optimization

When I was writing this Lab, I ran into a lot of bugs when running tests, and I felt numb. Looking at my git records, I found that the code was generally written from 5:00 to 6:30, and then I adjusted the bugs for another three or four hours. . . :

The main optimization point of this Lab is to remember to use std::move to forward strings. Then this is the speed at which I advance the buffer first and then the stream regardless of whether the string can directly enter the stream.

This is the speed after my special processing of this situation. You can see that it has reached the speed of 11 + Gbit/s. It stands to reason that my buffer entry operation is just an extra run of the linked list for this situation. I didn’t expect the speed to be as high as 11 + Gbit/s. Quite a bit different:

Finally, look at the number of lines of code and run ./scripts/lines-of-code. If an error is reported, you need to install a tool sudo apt-get install sloccount:

It said that the basic code is 22 lines, but we wrote 77 lines. I looked at the statistical line count and actually removed comments and blank lines. He said that 50-60 lines is normal. I wrote it in more detail here. It’s not impossible to suppress lines even if you want to, it’s about the same.

Article directory

Foreword

Other notes

Related links

1. Getting started

2. Putting substrings in sequence

2.1 Requirements Analysis

2.2 Notes

2.3 Code Implementation

3. Testing and optimization