n*******7
发帖数: 181 | 1 放假，终于有时间run GDB，才对老魏的程序有些理解了。仍然有些疑问。想向老魏和
大家请教。
先陈述一下基本的理解：
TrainTicketMap 是关键的数据库，表征对应车次当前所有空座. 它是一个二维数组，
两个indices分别是起始站和（站数 - 1). 它的值是一个stack（由单向链实现）。
stack上每一元素对应一个座位的站次间的空座范围，表示此座位从该起始站开始数该
站数范围内是空的。该元素的next指针指向stack上下一个对应不同座位的元素。
在初始状态，每个座位从起始站0开始10站都空，所以这个二维数组只在index［0，9］
有非空stack，里面压了对应所有座位的3000个元素，座位1在最上。假设第一个请求是
起始站3站数1，则座位1从站3到站4被出票，该座位空座范围［起始站，站数－1］从［
0，9］变为［0，2］和［4，5］。所以，对这个二维数组的操作（reserve函数里）是
：座位1在index［0，9］stack上的元素被free回TicketPool，从TicketPool重新
allocate两个元素给座位1，分别压进在index［0，2］和［4，5］的stacks。
整个操作分两步：allocate(); reserve().
allocate() 在TrainTicketMap找覆盖所请求站次的空座范围。搜索范围是顺着预先设
定的SearchOffsets，从小到大。所用时间较大而且不定，只读而不修改在
TrainTicketMap。是非transaction部分。
reserve() 是transaction部分，修改TrainTicketMap，用时很少并且固定。
请问，上述理解对吗？
我有几个问题：
1. 对站数能scale吗？如果站数从10变成100，TrainTicketMap与站数^2成正比，搜索
范围就增大100倍。allocate（）时间就增大100倍。当然可以用一个dedicated core
做reserve，把allocate分散到其它cores上。但如何同步就需要一些比较细碎的设计，
不如现在这样简洁了。另外，估计现有的core数很难消化得了100倍的计算量。所以，
对100站是不是就很难达到1M/s的指标了？
2. 如果朝实际方向再进一步，支持一个请求内多个座位连座，该怎么做？这应该是非
常贴近真实需要的。一家人一起走，座位应该是一起买，坐在一起的吧？如果顺着同样
的算法，TrainTicketMap是不是就该扩展成四维，多出的两维是起始座和座位数。那么
，搜索范围就扩大3000^2倍。这个算法是不是就不现实了？
3. 这个算法是源于成熟的理论，还是老魏或老姜的原创？无论如何，针对赌约的指标
要求，解决得非常精巧漂亮，令人佩服。这个问题，在逻辑上相当于在一个二维空间（
两轴分别是座位和站）不空的点上画叉叉，然后找可以容下长（连续座位数）宽（站数
）align在起始站的长方形的空域。这是不是另外还有更generic更好scale的理论和算
法？ |
T********i
发帖数: 2416 | 2 不敢当，我们可以讨论一下。
首先，这个算法是老姜原创。2年多以前他就贴出来过。很不幸立刻淹没在一大堆口水
帖中。这也证明了这个版根本不是严肃讨论技术的地方。我只不过在实现过程中做了一
些优化而已。这个事实我已经反复生命过，不敢掠人之美。
1。站数scalability肯定不好，算法本身很简单。站数从10变成100，allocate（）时
间就增大100倍。这个是肯定的。但是我们讨论的是火车票，不是汽车票。100站现实中
不可能。20站有没有可能我不知道。20站allocate()就要慢四倍。但是可以接受。
2。多个座位连坐的问题。这个倒是不用3000^2倍。其实如果把TrainTicketMap稍加改
变，座位不是stack而是bitmap的话，就会容易很多。搜索连坐估计可以做到O(m^2 ×
log(n))，m是站数，n是座位数；实际代价可以很小。
其实我现在的算法实现也很仓促。比如现在的TrainTicketMap是一个矩形，实际上只用
了一半，就是沿对角线的三角形而已。主要是我看指标远远超过了，就将就了。
事实上，这个算法很适合scale到外围机上去。这也是我故意分两步allocate和reserve
的原因。外围机通过allocate算法可以filter大量的无效请求。而且这个算法能够线性
分布到多核上面去。
至于复杂业务逻辑，可以选择在外围机或者核心机实现，或者both。
其实我认为，相对于算法，大家更应该思考架构的问题。不论业务逻辑复杂与否，这种
耦合问题究竟应该采用何种架构？当然考虑问题要全面，实现，维护，运营成本都要考
虑。简单逻辑你说不考虑公平和运营成本，把3000数据库当分布式计数器用。那么难道
稍微复杂的业务逻辑数据库就能够更优化？给我写一个query看看？ |
w********m
发帖数: 1137 | 3 个人觉得，魏老师的这个解决方案是一个高频交易的classic demo codebase。要进东
部银行的可以好好看看。
CPU比memory快10倍，memory比SSD快10倍，SSD比hard disk快10倍。hard disk比网线
快10倍。
魏老师告诉我们，高频交易最重要的是全内存运行，规避磁盘的IO限制。实现毫秒级的
transaction，一定要单机高并发。这是为什么东部银行喜欢折磨C＋＋的原因。
像12306这样的电商，瓶颈在磁盘和网线。DB建在磁盘上面，所以一定要选性能最好的
DB。 网线的堵塞没办法，只有靠买CDN来解决。电商大部分的钱都花在这方面了。
魏老师的性能再好，估计也不能改变磁盘和网线的物理限制。所以。。。 |
T********i
发帖数: 2416 | 4 其实吧，倒不如说该用啥就用啥。指望啥都有现成的，还要你干啥？
你现在，离磁盘和网线的物理限制还差的很远。大概有数量级的差别吧。比如，10G，
40G网卡现在大把。一台server装两块，就是20-80G。能服务多少12306并发用户？
我们谈架构，throughput是最重要的性能指标。所以我当年第一贴就说了，别的都是浮
云，只要拿出throughput就好了。比如我系统能持续多大的throughput，20G,40G,80G
？这事儿，和单机多机真的无关。
【在 w********m 的大作中提到】
: 个人觉得，魏老师的这个解决方案是一个高频交易的classic demo codebase。要进东
: 部银行的可以好好看看。
: CPU比memory快10倍，memory比SSD快10倍，SSD比hard disk快10倍。hard disk比网线
: 快10倍。
: 魏老师告诉我们，高频交易最重要的是全内存运行，规避磁盘的IO限制。实现毫秒级的
: transaction，一定要单机高并发。这是为什么东部银行喜欢折磨C＋＋的原因。
: 像12306这样的电商，瓶颈在磁盘和网线。DB建在磁盘上面，所以一定要选性能最好的
: DB。 网线的堵塞没办法，只有靠买CDN来解决。电商大部分的钱都花在这方面了。
: 魏老师的性能再好，估计也不能改变磁盘和网线的物理限制。所以。。。
|
r***6
发帖数: 401 | 5 Use bitmask makes great sense. If we assume at most 32 stations, then a
single uint32_t (unsigned) can represent one seat availability. A single
train seatmap is just an array of unsigned. Assume 4096 seats per train,
then the entire one train seatmap is only 16KB.
The reserve function would look like this:
unsigned _seatmap[NSEATS];
int Train::reserve(int start, int length)
{
//return seat index reserved, -1 if not available
unsigned mask = ((1 << length)-1) << start;
for (unsigned *seat = _seatmap; seat<_seatmap+NSEATS; ++seat) {
if (!(*seat & mask)) {
*seat |= mask;
return seat - _seatmap;
}
}
return -1;
}
This is essentially a linear search, but should be really fast because
almost all seat is within cache and access is linear. Each match is just a
32bit bitwise AND operation. |
m*p
发帖数: 1331 | 6 确实是hft里面经常看到的高性能单机版无io的东西。
【在 w********m 的大作中提到】
: 个人觉得，魏老师的这个解决方案是一个高频交易的classic demo codebase。要进东
: 部银行的可以好好看看。
: CPU比memory快10倍，memory比SSD快10倍，SSD比hard disk快10倍。hard disk比网线
: 快10倍。
: 魏老师告诉我们，高频交易最重要的是全内存运行，规避磁盘的IO限制。实现毫秒级的
: transaction，一定要单机高并发。这是为什么东部银行喜欢折磨C＋＋的原因。
: 像12306这样的电商，瓶颈在磁盘和网线。DB建在磁盘上面，所以一定要选性能最好的
: DB。 网线的堵塞没办法，只有靠买CDN来解决。电商大部分的钱都花在这方面了。
: 魏老师的性能再好，估计也不能改变磁盘和网线的物理限制。所以。。。
|
w********m
发帖数: 1137 | 7 单数据中心，运营商能给的稳定带宽能有100MB/s就不错了。每个新用户第一次登陆可
能就下载100KB，想象一下1000个用户同时浏览。
所以理想很丰满，现实总是很残酷。
80G
【在 T********i 的大作中提到】
: 其实吧，倒不如说该用啥就用啥。指望啥都有现成的，还要你干啥？
: 你现在，离磁盘和网线的物理限制还差的很远。大概有数量级的差别吧。比如，10G，
: 40G网卡现在大把。一台server装两块，就是20-80G。能服务多少12306并发用户？
: 我们谈架构，throughput是最重要的性能指标。所以我当年第一贴就说了，别的都是浮
: 云，只要拿出throughput就好了。比如我系统能持续多大的throughput，20G,40G,80G
: ？这事儿，和单机多机真的无关。
|
T********i
发帖数: 2416 | 8 实际情况比这个复杂一些。连座加上最小碎片检索可能需要先Or最多55种可能性，然后
再搜索。
AVX + prefetch每cycle处理512 bit是有可能的。
【在 r***6 的大作中提到】
: Use bitmask makes great sense. If we assume at most 32 stations, then a
: single uint32_t (unsigned) can represent one seat availability. A single
: train seatmap is just an array of unsigned. Assume 4096 seats per train,
: then the entire one train seatmap is only 16KB.
: The reserve function would look like this:
: unsigned _seatmap[NSEATS];
: int Train::reserve(int start, int length)
: {
: //return seat index reserved, -1 if not available
: unsigned mask = ((1 << length)-1) << start;
|
T********i
发帖数: 2416 | 9 你就别闹了。照你的算法，Google和好虫他们Netflix用户都可以吃屎去了。
【在 w********m 的大作中提到】
: 单数据中心，运营商能给的稳定带宽能有100MB/s就不错了。每个新用户第一次登陆可
: 能就下载100KB，想象一下1000个用户同时浏览。
: 所以理想很丰满，现实总是很残酷。
:
: 80G
|
n*******7
发帖数: 181 | 10 感谢老魏的详尽回答！老姜的算法和老魏的实现都做得很漂亮。很同意关于架构的论述。
对多票连座如何实现仍有不解。能否具体说说“把TrainTicketMap稍加改变，座位不是
stack而是bitmap”和“连座加上最小碎片检索可能需要先Or最多55种可能性”？
TrainTicketMap的index是［起始站，站数－1］。在［起始站，站数－1］的stack上的
非零值表示对某座这个站的范围（起始站－》起始站＋站数－1）是空的。改成bitmap
是不是bitmap里的1bits和stack上的元素有相同的含义？从同一个［起始站，站数－1
］点上找到的多个座位很可能是不相连的，而相连的座位可能在不同的［起始站，站数
－1］点上，怎样找？ |
|
|
n*******7
发帖数: 181 | 11 这个做法没有考虑每一站的seatmap都是不同的而且中途不换座。另外，这个函数没有
处理跨word边界的情况，当然，这是小问题。
【在 r***6 的大作中提到】
: Use bitmask makes great sense. If we assume at most 32 stations, then a
: single uint32_t (unsigned) can represent one seat availability. A single
: train seatmap is just an array of unsigned. Assume 4096 seats per train,
: then the entire one train seatmap is only 16KB.
: The reserve function would look like this:
: unsigned _seatmap[NSEATS];
: int Train::reserve(int start, int length)
: {
: //return seat index reserved, -1 if not available
: unsigned mask = ((1 << length)-1) << start;
|
r***6
发帖数: 401 | 12 There is no word boundary problem because at most 32 stations therefore a
32bit unsigned represents one seat availability throughout all stations.
As for adjacent seat issue, we can extend to 64(2 seats) or 128 bit(four
seats in a row) If no adjacent seats available you can also try to find
available seats with minimal distance after first scan.
Like teacher Wei said if you optimize for sse/avx, it is possible to check
512bits in a cycle, or 16 seats per cycle. For 4096 seats, you only need 256
cycles, approaching 85ns (at 3GHz) in worst case.
The key here is to minimize memory footprint to have sequential cache memory
access most of the time. This should be able to achieve an order of
magnitude performance. |
r***6
发帖数: 401 | 13 1. 中途换座 probably is not a requirement. If really in need, this probably
should be a ticket exchange or reissue.
2. Not sure if I understand "每一站的seatmap都是不同". My definition of one
seat bitmap word is vertical (availability throughout stations for one
particular seat) not horizontal (a snapshot of seat availability at
particular station) if you think entire train seat bitmap is a matrix, the
layout is column major indexes first. It is important because one bitwise
AND operation can check if this seat is a match for the trip riding mask.
这个做法没有考虑每一站的seatmap都是不同的而且中途不换座。另外，这个函数没有
处理跨word边界的情况，当然，这是小问题。
【在 n*******7 的大作中提到】
: 这个做法没有考虑每一站的seatmap都是不同的而且中途不换座。另外，这个函数没有
: 处理跨word边界的情况，当然，这是小问题。
|
T********i
发帖数: 2416 | 14 还是代码说话吧：
增加了一个函数： allocate2
其目的是，找到所有符合条件的座位空间，放到一个数组里。数组大小是座位数（3000）
剩下的，愿意怎么找相邻座位都简单了。至于优化也很简单，就是找sum(碎片）最小的
相邻座位。
注意，allocate和reserve可以优化到不同的core上做pipeline。也就是机行代码的事
情。
void TrainTicketMap::allocate2(int start, int length, Ticket **seats) {
length--; // normalize to [0, 9]
for (Offsets::iterator it = offsets.begin(); it != offsets.end(); ++it) {
register int curStart = start + it->start;
register int curLength = length - it->start + it->length;
if (curStart >= 0 && curLength < SEGMENTS) {
//printf("Searching %d %d\n", curStart, curLength);
size_t index = curStart + curLength * SEGMENTS;
Ticket *cur = _map[index];
while (cur) {
seats[cur->_seat] = cur;
cur = cur->_next;
}
}
}
}
这个allocate2性能如何呢？
下面的代码基本上是worst case，每次都会收集满3000座位，而且促进最大cache miss。
static void benchmark() {
double t1 = getTime();
printf("start benchmark\n");
Ticket *seats[SEATS];
for (size_t i=0; i<10000000LL; i++) {
int train = rand() % TRAINS;
int start = rand() % SEGMENTS;
int length = rand() % (SEGMENTS - start);
if (length == 0) {
length = 1;
}
memset(seats, 0, sizeof(Ticket *) * SEATS);
trains[train]->allocate2(start, length, seats);
}
double t2 = getTime();
printf("Total time = %f\n", t2 - t1);
}
结果：1000万张票大约34秒。
所以如果支持无限连座，worst case大约30万票/s。Best case可以多核并行，仍然能
超过1000万。
注意，allocate2仍然能够无限scalable。所以查询的throughput基本是无限的。 |
n*******7
发帖数: 181 | 15 My bad. I misunderstood seatmap as one bit per seat. You actually mean one
bit per station.
So, it is just scanning the array of seats with complexity of O(seats).
TrainTicketsMap is not used. Right?
256
memory
【在 r***6 的大作中提到】
: There is no word boundary problem because at most 32 stations therefore a
: 32bit unsigned represents one seat availability throughout all stations.
: As for adjacent seat issue, we can extend to 64(2 seats) or 128 bit(four
: seats in a row) If no adjacent seats available you can also try to find
: available seats with minimal distance after first scan.
: Like teacher Wei said if you optimize for sse/avx, it is possible to check
: 512bits in a cycle, or 16 seats per cycle. For 4096 seats, you only need 256
: cycles, approaching 85ns (at 3GHz) in worst case.
: The key here is to minimize memory footprint to have sequential cache memory
: access most of the time. This should be able to achieve an order of
|
n*******7
发帖数: 181 | 16 谢谢老魏！确实用代码说话是最清楚的。：）
理解你的做法了。每次memset清空seat数组，找出所有的范围，排出所有seats，然后
找连座和优化碎片就容易了。我没往这个方向想是因为以为这样会慢(O(n) complexity
)，现在看你的benchmark确实performance也还不错。
多谢多谢！
3000）
) {
【在 T********i 的大作中提到】
: 还是代码说话吧：
: 增加了一个函数： allocate2
: 其目的是，找到所有符合条件的座位空间，放到一个数组里。数组大小是座位数（3000）
: 剩下的，愿意怎么找相邻座位都简单了。至于优化也很简单，就是找sum(碎片）最小的
: 相邻座位。
: 注意，allocate和reserve可以优化到不同的core上做pipeline。也就是机行代码的事
: 情。
: void TrainTicketMap::allocate2(int start, int length, Ticket **seats) {
: length--; // normalize to [0, 9]
: for (Offsets::iterator it = offsets.begin(); it != offsets.end(); ++it) {
|
T********i
发帖数: 2416 | 17 其实还有很多可以讨论的。比如，复杂搜索例如连座之类，是否放在外围机比较好？这
样，核心机出票保证>1000万/s没有问题。
还有，我开始确实考虑每个座位block用bitmap，这样3000要375 bytes。当然OR操作要
用AVX加速。memory带宽需求显著增加，但是实际上不见得比我的allocate2慢。当然需
要实际测才知道。
至于3000数据库并行，我还真希望qxc写个query出来，别的不说，先把单张票优化一下
给我看看？
另外，这个worst case实际上是不会发生的。即使10%请求都是连座的，性能依然远超
1M/s。
至于12306用的gemfire内存数据库，gemfire还是靠Bear Stearns发家的。那时期我还
在Bear Stearns prop desk做Associate Director。具体情况我还是比较了解的。我不
认为gemfire在系统中能够起到任何关键作用。 |
n*******7
发帖数: 181 | 18 reserve() 是应该在一个dedicated的core上以保证速度。复杂搜索可以offload到其它
cores上。你说的外围机是这些cores，还是真正的机子？如果是真正的机子，memory不
在一个系统内，还需要一些message queue的设计吧？
bitmap有可能更快。既然支持AVX，memory带宽应该够吧。
12306的瓶颈估计还是在IO，而不是这些内存操作。
我还有一个不清楚的地方，就是如何处理退票。如果付款出错，就需要把票返回到
TrainTicketsMap里，另外还需要合并原来被此票分裂的范围。这是不是也对称地分两
步，先搜索被此票分裂的范围，再进transaction写进map里？
【在 T********i 的大作中提到】
: 其实还有很多可以讨论的。比如，复杂搜索例如连座之类，是否放在外围机比较好？这
: 样，核心机出票保证>1000万/s没有问题。
: 还有，我开始确实考虑每个座位block用bitmap，这样3000要375 bytes。当然OR操作要
: 用AVX加速。memory带宽需求显著增加，但是实际上不见得比我的allocate2慢。当然需
: 要实际测才知道。
: 至于3000数据库并行，我还真希望qxc写个query出来，别的不说，先把单张票优化一下
: 给我看看？
: 另外，这个worst case实际上是不会发生的。即使10%请求都是连座的，性能依然远超
: 1M/s。
: 至于12306用的gemfire内存数据库，gemfire还是靠Bear Stearns发家的。那时期我还
|
T********i
发帖数: 2416 | 19 单机内，不相关搜索可以offload到多核，所以实际性能应该远远超过1M/s。除非像
goodbug和zhaoce那样专门选最恶劣的sequence来测试。
外围机是真正的机子，本来就需要message queue设计，这个我说过多次了，机制和hot
standby recovery一样。其实，设计中，任何外围机都能当hot standby使用的。
这种load，多机间multicast sync状态基本能够达到latency微秒级别。
退票反正也不多。是一个worst case O(SEATS)的过程。实际性能最差应该在单核每秒
20万-30万票。平均应该远超。
【在 n*******7 的大作中提到】
: reserve() 是应该在一个dedicated的core上以保证速度。复杂搜索可以offload到其它
: cores上。你说的外围机是这些cores，还是真正的机子？如果是真正的机子，memory不
: 在一个系统内，还需要一些message queue的设计吧？
: bitmap有可能更快。既然支持AVX，memory带宽应该够吧。
: 12306的瓶颈估计还是在IO，而不是这些内存操作。
: 我还有一个不清楚的地方，就是如何处理退票。如果付款出错，就需要把票返回到
: TrainTicketsMap里，另外还需要合并原来被此票分裂的范围。这是不是也对称地分两
: 步，先搜索被此票分裂的范围，再进transaction写进map里？
|
n*******7
发帖数: 181 | 20 懂了，多谢！
多机间multicast sync状态真能达到latency微秒级别吗？throughput是没问题的。但
是，就单个ticket的latency来说，上下两边的protocal stack就要花不少时间吧，再
加上处理message queue的延迟(到queue里也不一定能马上处理），能压缩到微秒级
吗？我没实际测过，不知道。能否说说在实际HFT系统里的message，除去网络的
延迟，在机子里传递过程需要多少时间？
hot
【在 T********i 的大作中提到】
: 单机内，不相关搜索可以offload到多核，所以实际性能应该远远超过1M/s。除非像
: goodbug和zhaoce那样专门选最恶劣的sequence来测试。
: 外围机是真正的机子，本来就需要message queue设计，这个我说过多次了，机制和hot
: standby recovery一样。其实，设计中，任何外围机都能当hot standby使用的。
: 这种load，多机间multicast sync状态基本能够达到latency微秒级别。
: 退票反正也不多。是一个worst case O(SEATS)的过程。实际性能最差应该在单核每秒
: 20万-30万票。平均应该远超。
|
|
|
T********i
发帖数: 2416 | 21 上kernel bypass的10G网卡。我的一个系统，如果进来的market data tick恰好
trigger一个order，用corvil分光测wire-to-wire的速度（half round trip），
median在10us以内，最大的outlier也在20us以内。
实测ping-pong，median 5us左右吧。
我们这种load，latency控制在20us以内没问题。
注意，我现在的实现，针对1G网卡的throughput做了些优化。比如尽量pool输出到一个
MTU以上(1400 bytes)。如果用10G网卡，可以用不同的优化方案。
【在 n*******7 的大作中提到】
: 懂了，多谢！
: 多机间multicast sync状态真能达到latency微秒级别吗？throughput是没问题的。但
: 是，就单个ticket的latency来说，上下两边的protocal stack就要花不少时间吧，再
: 加上处理message queue的延迟(到queue里也不一定能马上处理），能压缩到微秒级
: 吗？我没实际测过，不知道。能否说说在实际HFT系统里的message，除去网络的
: 延迟，在机子里传递过程需要多少时间？
:
: hot
|
n*******7
发帖数: 181 | 22 很有用的数据，谢谢！希望这里多些这样实用的信息，比吵架有意义多了。:)
优化到这个数量级差不多是到头了。在这点时间里跑不了多少business logic。 |
y*****r
发帖数: 327 | |
T********i
发帖数: 2416 | 24 我用了很多年solarflare。这个pc12306还真没上solarflare。性能足够了。
【在 y*****r 的大作中提到】
: 这是上了solarflare以后的数据？
|
y*****r
发帖数: 327 | 25 谢谢回答，我是说你5-20微秒的测试是不是solarflare/openonload 之后的数据。
【在 T********i 的大作中提到】
: 我用了很多年solarflare。这个pc12306还真没上solarflare。性能足够了。
|
T********i
发帖数: 2416 | 26 是。Solarflare卖这么贵就是因为latency低。
【在 y*****r 的大作中提到】
: 谢谢回答，我是说你5-20微秒的测试是不是solarflare/openonload 之后的数据。
|
y*****r
发帖数: 327 | 27 从send（）到wire大概多少延时？谢谢。
【在 T********i 的大作中提到】
: 是。Solarflare卖这么贵就是因为latency低。
|
T********i
发帖数: 2416 | 28 3-5us吧。
【在 y*****r 的大作中提到】
: 从send（）到wire大概多少延时？谢谢。
|
n*******7
发帖数: 181 | 29 这3-5us是不是主要在加每层header,每加一层要把payload memcpy一下？
如果追究一下极限，在两个直接连接的机子上，用proprietary protocol，不用支持通
常的protocol，所以不用一层层加header，网卡直接DMA数据到cache里，不知道这样的
物理极限是多少。
【在 T********i 的大作中提到】
: 3-5us吧。
|
y*****r
发帖数: 327 | 30 但前面说ping pong 是5微秒？
【在 T********i 的大作中提到】
: 3-5us吧。
|
|
|
T********i
发帖数: 2416 | 31 极限就是PCI-E Latency。Solarflare号称half round trip最低3.X us。根据我的经验
偶尔能够达到。当然我多少有点business logic在里面。
infiniband latency更低，但是没有轮子用它。
【在 n*******7 的大作中提到】
: 这3-5us是不是主要在加每层header,每加一层要把payload memcpy一下？
: 如果追究一下极限，在两个直接连接的机子上，用proprietary protocol，不用支持通
: 常的protocol，所以不用一层层加header，网卡直接DMA数据到cache里，不知道这样的
: 物理极限是多少。
|
T********i
发帖数: 2416 | 32 half round trip.
【在 y*****r 的大作中提到】
: 但前面说ping pong 是5微秒？
|
m*****k
发帖数: 731 | 33 :假设第一个请求是
:起始站3站数1，则座位1从站3到站4被出票，该座位空座范围［起始站，站数－1］从［
:0，9］变为［0，2］和［4，5］。
为啥不是 ［0，3］和［4，5］?
:它是一个二维数组，
这样有何妙处啊？ |
n*******7
发帖数: 181 | 34 我曾经测过PCIe latency. 用CPU back to back读写PCIe device 同一个32-bit
register, 每次需要500ns。你看到3-5us时你的packet有多少bytes？不知道是
不是同一个cacheline的数据都能在同一个500ns里完成，不然很难解释一个packet
（假设64 bytes）能在几个us内完成。
【在 T********i 的大作中提到】
: 极限就是PCI-E Latency。Solarflare号称half round trip最低3.X us。根据我的经验
: 偶尔能够达到。当然我多少有点business logic在里面。
: infiniband latency更低，但是没有轮子用它。
|
n*******7
发帖数: 181 | 35 站数是3，站数－1是2， 所以是［0，2］
就是个记录空座范围的方式，在stack 里O(1)找到空座。
从［ |
m*****k
发帖数: 731 | 36 多谢回复，
用个例子来说吧，
假如只有一次车，从北京到广州，共4站，
s0(北京)， s1(天津)， s2(上海)， s3(广州)，s表示station
车上只有两个座位： seat1, seat2
初始状态：
arr[0,0] 表示s0 到 s1的空座位集合，空Stack
...
arr[0,1] 表示s0 到 s2的空座位集合，空Stack
...
arr[0,2] 表示s0 到 s3的空座位集合，a Stack { seat1 , seat2}，
...
没出票时，只有arr[0,2] 有非空值 { seat1 , seat2}，
我的理解对吗？
站数是3，站数－1是2， 所以是［0，2］
就是个记录空座范围的方式，在stack 里O(1)找到空座。
从［
【在 n*******7 的大作中提到】
: 站数是3，站数－1是2， 所以是［0，2］
: 就是个记录空座范围的方式，在stack 里O(1)找到空座。
: 从［
|
n*******7
发帖数: 181 | 37 你的理解是对的。
code中的变量名ticket有点misleading。这其实是某座在站之间的空座范围。这个数组
＋stack存着所有范围。如果有一个空座，它必然在某个范围之内。所有范围的集合表
征所有空座。数组是这些范围的存储和索引方式。
【在 m*****k 的大作中提到】
: 多谢回复，
: 用个例子来说吧，
: 假如只有一次车，从北京到广州，共4站，
: s0(北京)， s1(天津)， s2(上海)， s3(广州)，s表示station
: 车上只有两个座位： seat1, seat2
: 初始状态：
: arr[0,0] 表示s0 到 s1的空座位集合，空Stack
: ...
: arr[0,1] 表示s0 到 s2的空座位集合，空Stack
: ...
|
m*****k
发帖数: 731 | 38 那为啥用这种索引方法呢？
arr[i,j] i 和 j 表示不同东西，其妙处何在？
就我举的例子而言，如果第一个请求是出一张从s1到s2的票，
这个算法是如何迅速找到arr[0,2] 中的seat1的呢？
arr[1,0]是空栈啊。
为啥不用
arr[i，j]表示从si到sj的空座集合呢？
从没用过cpp，看不懂老魏的代码，恳求好心人能精辟的指点一下，毕竟算法是不需要
用特定language来解释的。
【在 n*******7 的大作中提到】
: 你的理解是对的。
: code中的变量名ticket有点misleading。这其实是某座在站之间的空座范围。这个数组
: ＋stack存着所有范围。如果有一个空座，它必然在某个范围之内。所有范围的集合表
: 征所有空座。数组是这些范围的存储和索引方式。
|
T********i
发帖数: 2416 | 39 最少56bytes, 最多1500bytes。
inbound UDP, outbound TCP。
其实Intel有trick。你搜一下Intel Data Direct I/O。直接PCI- E到LLC(Last level
cache)。甚至一个memory读写都不需要。
读一下Intel的白皮书。这些年各种花样层出不穷。这也是延续摩尔定律的一种方式。
其实，这才是新玩意儿。比起来分布式才是上个世纪的。这些东西的玩法，5年前都不
可能。
【在 n*******7 的大作中提到】
: 我曾经测过PCIe latency. 用CPU back to back读写PCIe device 同一个32-bit
: register, 每次需要500ns。你看到3-5us时你的packet有多少bytes？不知道是
: 不是同一个cacheline的数据都能在同一个500ns里完成，不然很难解释一个packet
: （假设64 bytes）能在几个us内完成。
|
m*****k
发帖数: 731 | 40 可以请教一下魏老师和老姜为啥用［起始站号，站数 - 1］来做index呢？
如果arr[i,j] 存所有座位的bitmap，i，j是起始，终止站号，查询空座位不是O(1)么？
×
【在 T********i 的大作中提到】
: 不敢当，我们可以讨论一下。
: 首先，这个算法是老姜原创。2年多以前他就贴出来过。很不幸立刻淹没在一大堆口水
: 帖中。这也证明了这个版根本不是严肃讨论技术的地方。我只不过在实现过程中做了一
: 些优化而已。这个事实我已经反复生命过，不敢掠人之美。
: 1。站数scalability肯定不好，算法本身很简单。站数从10变成100，allocate（）时
: 间就增大100倍。这个是肯定的。但是我们讨论的是火车票，不是汽车票。100站现实中
: 不可能。20站有没有可能我不知道。20站allocate()就要慢四倍。但是可以接受。
: 2。多个座位连坐的问题。这个倒是不用3000^2倍。其实如果把TrainTicketMap稍加改
: 变，座位不是stack而是bitmap的话，就会容易很多。搜索连坐估计可以做到O(m^2 ×
: log(n))，m是站数，n是座位数；实际代价可以很小。
|
|
|
n*******7
发帖数: 181 | 41 这个问题老魏可能有更好回答。就我的理解，“arr[i，j]表示从si到sj的空座集合”
也完全可以。
［上车站，站数］和［上车站，下车站］是一一对应，完全等效的。我看不出有什么
tradeoff。
在TrainTicketMap::allocate（）里，用Offsets iterator遍历所有可能范围。其实这
里如果不用
C++的iterator遍历固定的SearchPatterns，直接用C的办法对两个indices用两层for
loop，
loop的range可变，还可以跳过一些entry，省了if (curStart >= 0 && curLength <
SEGMENTS)，
会更快一些。老魏估计是因为足够快就不讲究了。 |
m*****k
发帖数: 731 | 42 多谢nanxiang7！
我就是觉得虽然实际上等效但为何要多余算一下站数-1，故而好奇老姜和老魏为何选这
个.
谢谢你confirm了查询是brute force,我可以好好睡觉了，:-p
【在 n*******7 的大作中提到】
: 这个问题老魏可能有更好回答。就我的理解，“arr[i，j]表示从si到sj的空座集合”
: 也完全可以。
: ［上车站，站数］和［上车站，下车站］是一一对应，完全等效的。我看不出有什么
: tradeoff。
: 在TrainTicketMap::allocate（）里，用Offsets iterator遍历所有可能范围。其实这
: 里如果不用
: C++的iterator遍历固定的SearchPatterns，直接用C的办法对两个indices用两层for
: loop，
: loop的range可变，还可以跳过一些entry，省了if (curStart >= 0 && curLength <
: SEGMENTS)，
|
z****e
发帖数: 54598 | 43
这个算法有啥难看懂的？
基本上都是暴力解
其实就是一个简单的计数器
早就说了，一旦分布并发遇到了困难
的就回去用单机
这是老魏的解法的唯一思路
蠢不可及
【在 m*****k 的大作中提到】
: 多谢nanxiang7！
: 我就是觉得虽然实际上等效但为何要多余算一下站数-1，故而好奇老姜和老魏为何选这
: 个.
: 谢谢你confirm了查询是brute force,我可以好好睡觉了，:-p
|
n*******7
发帖数: 181 | 44 按你的表达法，如果座0在站3到站5间有空，arr[3,5] 的bit0是1，arr[3,4］和arr[4,
5]的bit0 是1吗？
老魏的做法，在查询的时候需要看多个点，在出票的时候（transaction）只需要变一
到三个。如果
你查询时是O（1），在出票时需要改写多少地方？
么？
【在 m*****k 的大作中提到】
: 可以请教一下魏老师和老姜为啥用［起始站号，站数 - 1］来做index呢？
: 如果arr[i,j] 存所有座位的bitmap，i，j是起始，终止站号，查询空座位不是O(1)么？
:
: ×
|
n*******7
发帖数: 181 | 45 至少在这个问题上，不是因为分布并发遇到了困难就回去用单机，而是针对这个问题本
身的scale在设计合理把transaction精简后单机完全可以胜任。
当然分布有很多高深的技术。但对赌约的指标老魏的code不是完全解决了问题吗？
【在 z****e 的大作中提到】
:
: 这个算法有啥难看懂的？
: 基本上都是暴力解
: 其实就是一个简单的计数器
: 早就说了，一旦分布并发遇到了困难
: 的就回去用单机
: 这是老魏的解法的唯一思路
: 蠢不可及
|
n*******7
发帖数: 181 | 46 我知道有这个trick，可以省CPU读packet 的时间。但就单个packet的latency来说，把
数据从wire上运
到LLC里，还是要花时间的，不知道占了3-5us中多大的部分。
level
【在 T********i 的大作中提到】
: 最少56bytes, 最多1500bytes。
: inbound UDP, outbound TCP。
: 其实Intel有trick。你搜一下Intel Data Direct I/O。直接PCI- E到LLC(Last level
: cache)。甚至一个memory读写都不需要。
: 读一下Intel的白皮书。这些年各种花样层出不穷。这也是延续摩尔定律的一种方式。
: 其实，这才是新玩意儿。比起来分布式才是上个世纪的。这些东西的玩法，5年前都不
: 可能。
|
w**z
发帖数: 8232 | 47 对于互联网的应用，追求us 级别的优化真的让人无语。
【在 n*******7 的大作中提到】
: 我知道有这个trick，可以省CPU读packet 的时间。但就单个packet的latency来说，把
: 数据从wire上运
: 到LLC里，还是要花时间的，不知道占了3-5us中多大的部分。
:
: level
|
z****e
发帖数: 54598 | 48 txn哪里精简了？
把一个从买票订票到最后金钱划账简化成一个内存中的int赋值操作
你见过哪个txn是原子操作的？
如果都是原子操作，还要txn干什么？
话说你啥时候见过金钱交易是简单的int的赋值操作？
这不是遇到困难就回去用单机是什么？
【在 n*******7 的大作中提到】
: 至少在这个问题上，不是因为分布并发遇到了困难就回去用单机，而是针对这个问题本
: 身的scale在设计合理把transaction精简后单机完全可以胜任。
: 当然分布有很多高深的技术。但对赌约的指标老魏的code不是完全解决了问题吗？
|
z****e
发帖数: 54598 | 49
对于大多数互联网的金钱交易来说
最大的latency来自pc到网站，或者说来自公网的路由器上的迟滞
这是一
其次，对于互联网的金钱交易来说
第二大的latency来自你系统本身跟merchant还有acquirer也就是银行等金钱存放系统
的io
因为这两步都需要经过公网，而且可能是跨地域操作
这里面的latency绝对是ms级的，甚至10，100ms级的
你在这个时候拼命优化一台单机的效率，4 what？
你有这个功夫，把路由好好优化一下，兴许更快
而且对于这种交易来说，txn往往是涉及到多个不同系统之间的协调
如果只是内存中的原子操作，还做个屁啊
要你做？
就好比人家要你做台汽车
你举了个轮子一路滚过去
因为汽车也用了轮子
这叫汽车？
老魏的解决方案解决了毛问题
从一开始的单机到最后拼命在外围机加机器
同时拼命简化需求，还有这样的？
现实中做系统，ba提了一个需求，你说，这个太麻烦
这不做，那不做，我就做最简单的i++
那你说ba会怎么办？第二天你就卷铺盖滚蛋了
【在 n*******7 的大作中提到】
: 至少在这个问题上，不是因为分布并发遇到了困难就回去用单机，而是针对这个问题本
: 身的scale在设计合理把transaction精简后单机完全可以胜任。
: 当然分布有很多高深的技术。但对赌约的指标老魏的code不是完全解决了问题吗？
|
z****e
发帖数: 54598 | 50
第一个，12306的票的数据肯定不在内存中
你想过如何从不同的分布式db中读取你需要的数据么？
老魏的想法很简单，就是直接从local disk上读出来
你觉得这个现实么？
就这么一个简单的需求，就搞死你了，别谈后面的了
说到底就是一个单机计数器
因为计数器这不管那不管，只管i++
这个你要有兴趣，自己做一个for loop，然后测一下各个硬件的能够爬到的最高i
就这种了，有个鸟现实意义
之所以写软件，就是要有创造，就是要解决实际问题
而不是回避问题，老魏的所谓解决方案，就看他在不停滴躲避各种问题
最后自己都承认不是12306，是一个计数器了
现在还打算翻案咯？
我靠，如果谁敢继续说这个是12306的话，我就要发毒誓了
别自找没趣哦
【在 n*******7 的大作中提到】
: 放假，终于有时间run GDB，才对老魏的程序有些理解了。仍然有些疑问。想向老魏和
: 大家请教。
: 先陈述一下基本的理解：
: TrainTicketMap 是关键的数据库，表征对应车次当前所有空座. 它是一个二维数组，
: 两个indices分别是起始站和（站数 - 1). 它的值是一个stack（由单向链实现）。
: stack上每一元素对应一个座位的站次间的空座范围，表示此座位从该起始站开始数该
: 站数范围内是空的。该元素的next指针指向stack上下一个对应不同座位的元素。
: 在初始状态，每个座位从起始站0开始10站都空，所以这个二维数组只在index［0，9］
: 有非空stack，里面压了对应所有座位的3000个元素，座位1在最上。假设第一个请求是
: 起始站3站数1，则座位1从站3到站4被出票，该座位空座范围［起始站，站数－1］从［
|
|
|
a*********a
发帖数: 3656 | 51 今天什么意思，赵老给古总的专场追悼会？版主刚打扫完上一场集体追悼会的会场。
【在 z****e 的大作中提到】
:
: 第一个，12306的票的数据肯定不在内存中
: 你想过如何从不同的分布式db中读取你需要的数据么？
: 老魏的想法很简单，就是直接从local disk上读出来
: 你觉得这个现实么？
: 就这么一个简单的需求，就搞死你了，别谈后面的了
: 说到底就是一个单机计数器
: 因为计数器这不管那不管，只管i++
: 这个你要有兴趣，自己做一个for loop，然后测一下各个硬件的能够爬到的最高i
: 就这种了，有个鸟现实意义
|
T********i
发帖数: 2416 | 52 Intel DDIO paper号称data rate是250G。我估计有Initial fixed latency，我猜测有
1us左右。
【在 n*******7 的大作中提到】
: 我知道有这个trick，可以省CPU读packet 的时间。但就单个packet的latency来说，把
: 数据从wire上运
: 到LLC里，还是要花时间的，不知道占了3-5us中多大的部分。
:
: level
|
k******n
发帖数: 184 | 53
你这几个三番五次提的最关键最难解决的问题什么时候他们正面回答过了？
度个假回来看版里这气氛以为做出了什么惊天动地的solution把好虫打得心服口服，
说到底就是为自己面子设计赌约， 简化一切条件，做了个toy, 还真是劣币驱逐良币。
人目的是赢赌约啊， 不是做出什么东西解决问题， 我也认输罢了。
另外姓wei的当时是要3个人都接赌约的， 第三个人可是claim 这在单机版要能linear
scalability的， 这个单机版的toy硬件再怎么多核也linear scale不了。不过要是不
算进赌约也无妨， 反正我已经认输。
【在 z****e 的大作中提到】
:
: 第一个，12306的票的数据肯定不在内存中
: 你想过如何从不同的分布式db中读取你需要的数据么？
: 老魏的想法很简单，就是直接从local disk上读出来
: 你觉得这个现实么？
: 就这么一个简单的需求，就搞死你了，别谈后面的了
: 说到底就是一个单机计数器
: 因为计数器这不管那不管，只管i++
: 这个你要有兴趣，自己做一个for loop，然后测一下各个硬件的能够爬到的最高i
: 就这种了，有个鸟现实意义
|
z****e
发帖数: 54598 | 54
linear
对啊，本来来这里也就是看看各个硅谷公司大概用了什么技术
能够取长补短一下，看看如何解决问题
结果麻痹的，被一堆卖机器的给搞得乌烟瘴气的
一天到晚就是做点简单的计数器
真是恶心啊，还tmd说别人是娼
摆明了自己就是一娼嘛，说的都是上个世纪的过时的破烂
还非要跟人家打赌，搞得好像自己的东西宇宙第一一样
要真有那个本事，那就去竞标啊，去fb演讲啊
就像vert.x和netty的某个德国作者一样，去fb分享经验啊
麻痹的又没这个本事，那不行，去12306竞标也行啊
结果也不行，连电商都搞不出来，做了半死一个计数器
愚人愚己罢了，本来这些卖机器的老年人写的帖子就没几个人爱看
如果不是哗众取宠一番，估计大多数人都直接忽略了
非要到处恶心人，真是人至贱则无敌
【在 k******n 的大作中提到】
:
: 你这几个三番五次提的最关键最难解决的问题什么时候他们正面回答过了？
: 度个假回来看版里这气氛以为做出了什么惊天动地的solution把好虫打得心服口服，
: 说到底就是为自己面子设计赌约， 简化一切条件，做了个toy, 还真是劣币驱逐良币。
: 人目的是赢赌约啊， 不是做出什么东西解决问题， 我也认输罢了。
: 另外姓wei的当时是要3个人都接赌约的， 第三个人可是claim 这在单机版要能linear
: scalability的， 这个单机版的toy硬件再怎么多核也linear scale不了。不过要是不
: 算进赌约也无妨， 反正我已经认输。
|
k******n
发帖数: 184 | 55
我注册mitbbs本来也不久， 不喜欢别的版块乌烟瘴气刚进来以为找到了一片净土想好
好学习， 结果被姓wei的发言震惊了。还有几个捣乱唯恐天下不乱的id。
他们卖不卖机器我不知道，人品如何我也不提， 我只是觉得为了赢赌局而刻意简化条
件回避web services的瓶颈这样的初衷太low， 相反我宁愿输钱输面子也想学点新东西
。事实上看懂算法后其实我有办法压缩状态把姓wei的内存优化一截，不过我不想参加
和这个话题有关的任何事情了， 谁让我们打工的就是不如自由创业者任性。
还有件事情很奇怪， 我刚进本版没人认识我， 我也从来没说过我学校在FB或者能挣钱
怎么怎么样，好虫也从没倚仗过netflix， 但是在争论的时候总三番五次被对方提起公
司学校挣多少啥的，这一点我还真是费解，有理说理， 你主动提这个什么意思？ 更别
说那些威胁告hr的弱智行径了。
【在 z****e 的大作中提到】
:
: linear
: 对啊，本来来这里也就是看看各个硅谷公司大概用了什么技术
: 能够取长补短一下，看看如何解决问题
: 结果麻痹的，被一堆卖机器的给搞得乌烟瘴气的
: 一天到晚就是做点简单的计数器
: 真是恶心啊，还tmd说别人是娼
: 摆明了自己就是一娼嘛，说的都是上个世纪的过时的破烂
: 还非要跟人家打赌，搞得好像自己的东西宇宙第一一样
: 要真有那个本事，那就去竞标啊，去fb演讲啊
|
a*********a
发帖数: 3656 | 56 你的意思是，一个里里外外吵了两年年的问题，古德霸还被魏耍了？魏“刻意简化，回
避瓶颈”，射了个套，古德霸还直接就钻了？
这是贬低古德霸的智商呢，还是贬低古德霸的情商呢？
相反我宁愿输钱输面子也想学点新东西
【在 k******n 的大作中提到】
:
: 我注册mitbbs本来也不久， 不喜欢别的版块乌烟瘴气刚进来以为找到了一片净土想好
: 好学习， 结果被姓wei的发言震惊了。还有几个捣乱唯恐天下不乱的id。
: 他们卖不卖机器我不知道，人品如何我也不提， 我只是觉得为了赢赌局而刻意简化条
: 件回避web services的瓶颈这样的初衷太low， 相反我宁愿输钱输面子也想学点新东西
: 。事实上看懂算法后其实我有办法压缩状态把姓wei的内存优化一截，不过我不想参加
: 和这个话题有关的任何事情了， 谁让我们打工的就是不如自由创业者任性。
: 还有件事情很奇怪， 我刚进本版没人认识我， 我也从来没说过我学校在FB或者能挣钱
: 怎么怎么样，好虫也从没倚仗过netflix， 但是在争论的时候总三番五次被对方提起公
: 司学校挣多少啥的，这一点我还真是费解，有理说理， 你主动提这个什么意思？ 更别
|
k******n
发帖数: 184 | 57
还两年， 我刚进来几个星期看着那套做派都烦了， 这么吵下去威胁互相问候的整个版
都给污了， 你打人家脸人家不回重新开一个往复循环自说自话。 我的目的很简单，整
个topic赶紧结束所有人shut up最好。
接这赌约我压根儿就没在乎输赢，虽然知道赌约就这么几句话很可能钻空子刻意回避一
些难题，但是也就大致扫了几眼压根没细想就度假去了，只想着回来能看到东西赶紧结
束。goodbug是不是我这么想的我不知道，如果不是人家已经杀档也没办法看到你说他
智商情商有问题。
可是你总知道甲方乙方或者做软件外包的商业合同是啥样的吧？ 你也知道赌约中没有
说清楚的地方可以按照最坏解释原则吧？ 我都懒得挑刺认输赶紧结束他们高兴就好。
这样以来，不管赌约如何， code摆在那， 每个人有每个人的解读， 我不反对别人觉
得高深莫测，可我觉得这就是个美本cs 1**的 toy project， 当然我也承认有些c++的
语法我没看懂， 不过这program干了什么摆在那就是了。 看到姓wei的为1us的优化讨
论的煞有其事的模样真是逗，说到底现代真正的web services就特么不是这么做的，
因为做web的瓶颈就tm从来不在mem和local上: https://gist.github.com/jboner/
2841832
【在 a*********a 的大作中提到】
: 你的意思是，一个里里外外吵了两年年的问题，古德霸还被魏耍了？魏“刻意简化，回
: 避瓶颈”，射了个套，古德霸还直接就钻了？
: 这是贬低古德霸的智商呢，还是贬低古德霸的情商呢？
:
: 相反我宁愿输钱输面子也想学点新东西
|
a*********a
发帖数: 3656 | 58 你参赌了？我一直以为是老魏，老古，一对一。
【在 k******n 的大作中提到】
:
: 还两年， 我刚进来几个星期看着那套做派都烦了， 这么吵下去威胁互相问候的整个版
: 都给污了， 你打人家脸人家不回重新开一个往复循环自说自话。 我的目的很简单，整
: 个topic赶紧结束所有人shut up最好。
: 接这赌约我压根儿就没在乎输赢，虽然知道赌约就这么几句话很可能钻空子刻意回避一
: 些难题，但是也就大致扫了几眼压根没细想就度假去了，只想着回来能看到东西赶紧结
: 束。goodbug是不是我这么想的我不知道，如果不是人家已经杀档也没办法看到你说他
: 智商情商有问题。
: 可是你总知道甲方乙方或者做软件外包的商业合同是啥样的吧？ 你也知道赌约中没有
: 说清楚的地方可以按照最坏解释原则吧？ 我都懒得挑刺认输赶紧结束他们高兴就好。
|
k******n
发帖数: 184 | 59
应该是1 v 3， 我和另一个看不惯姓wei威胁告hr的ID作风损了他几句和质疑技术问题
，他叫嚣着让我们3个人都赌才肯开始(当时语气非常不客气好像是"3个孙子"之类的)，
并且还有时间限制。我就同意了， 就算我输了总比版里变那样好吧， 至少有代码可以
看到底是个toy还是个什么。
另外一个id似乎在linear scalability问题上把姓wei的呛的不敢回复，我也没仔细看
他是否应下了， 不过应该不在赌约中。 这个赌约其实就是裁判庄家都是一个人， 纯
粹为赢而设计的。 输了没什么， 不过这样挺low的， 跑在mem上的就把一个web
service有挑战的问题全回避了。
【在 a*********a 的大作中提到】
: 你参赌了？我一直以为是老魏，老古，一对一。
|
a*********a
发帖数: 3656 | 60 另一个是？
【在 k******n 的大作中提到】
:
: 应该是1 v 3， 我和另一个看不惯姓wei威胁告hr的ID作风损了他几句和质疑技术问题
: ，他叫嚣着让我们3个人都赌才肯开始(当时语气非常不客气好像是"3个孙子"之类的)，
: 并且还有时间限制。我就同意了， 就算我输了总比版里变那样好吧， 至少有代码可以
: 看到底是个toy还是个什么。
: 另外一个id似乎在linear scalability问题上把姓wei的呛的不敢回复，我也没仔细看
: 他是否应下了， 不过应该不在赌约中。 这个赌约其实就是裁判庄家都是一个人， 纯
: 粹为赢而设计的。 输了没什么， 不过这样挺low的， 跑在mem上的就把一个web
: service有挑战的问题全回避了。
|
|
|
m*****k
发帖数: 731 | 61
4,
yes
yes, 也是暴力循环，但我猜总的来说出票时暴力循环貌似比查询时暴力循环省油。而
且把相关arr[i,j]的bit0置0的操作应该和老魏查询时复杂度等同。
【在 n*******7 的大作中提到】
: 按你的表达法，如果座0在站3到站5间有空，arr[3,5] 的bit0是1，arr[3,4］和arr[4,
: 5]的bit0 是1吗？
: 老魏的做法，在查询的时候需要看多个点，在出票的时候（transaction）只需要变一
: 到三个。如果
: 你查询时是O（1），在出票时需要改写多少地方？
:
: 么？
|
n*******7
发帖数: 181 | 62 老魏的做法是有道理的。查询部分不改写state，可以offload到其它cores，可以允许
多个cores同时查询（只读不写不需加锁），所以慢些没有关系；出票部分因为改写
state，需要快并且minimize改写部分，并且用dedicated core以免锁提高效率。这种
读写不对称处理还是很常见的。
老魏没有把东西做到底，因为已经够快就收手了。下一步应该是用一个core专做出票，
其它多个cores同时查询。那样的瓶颈就在出票上。出票简洁，只需改写一处，好处就
会出来了。你的办法出票时得搜索和改写多个地方，因为改写所以又不能多个cores同
时做，除非先锁住，速度就慢了。 |
a*********a
发帖数: 3656 | 63 看了一下你参赌的经过，觉得你做事很有问题。
1. 如果你目光犀利，判断准确，看出了魏过分简化，回避瓶颈，是个圈套，就应该明
确指出来，同时叫古不要赌。
2. 如果古水平没你高，没有看破这个“过分简化，回避瓶颈”的套，或者他知识有缺
陷，认为简化了也是mission
impossible，或者他头脑发热感情用事。那你就不该同意。这样你自己显得尿一点，
但是赌局不开，古德霸ID就不会死。
3. 既然你接了，就该好好帮着古德霸。结果你撒手度假去了。完了古德霸苦巴巴的在
斑上央求人做case test，没人理。
4. 结果出了，古德霸立即执行了，你还在这里唧唧歪歪。
你们门萨俱乐部都是你这样的猪队友吗？怎么感觉1v3的赌局，你把古德霸给卖了？
如果你觉得"3个孙子"语气非常不客气，魏如果说“3个太监”你的幼小心灵该受到多大
创伤啊？
【在 k******n 的大作中提到】
:
: 应该是1 v 3， 我和另一个看不惯姓wei威胁告hr的ID作风损了他几句和质疑技术问题
: ，他叫嚣着让我们3个人都赌才肯开始(当时语气非常不客气好像是"3个孙子"之类的)，
: 并且还有时间限制。我就同意了， 就算我输了总比版里变那样好吧， 至少有代码可以
: 看到底是个toy还是个什么。
: 另外一个id似乎在linear scalability问题上把姓wei的呛的不敢回复，我也没仔细看
: 他是否应下了， 不过应该不在赌约中。 这个赌约其实就是裁判庄家都是一个人， 纯
: 粹为赢而设计的。 输了没什么， 不过这样挺low的， 跑在mem上的就把一个web
: service有挑战的问题全回避了。
|
s*******r
发帖数: 310 | 64 其实很简单，就是自以为是的人没赌品，输不起。
在我看来这帮输家比人赢家老魏还嚣张。
mission
【在 a*********a 的大作中提到】
: 看了一下你参赌的经过，觉得你做事很有问题。
: 1. 如果你目光犀利，判断准确，看出了魏过分简化，回避瓶颈，是个圈套，就应该明
: 确指出来，同时叫古不要赌。
: 2. 如果古水平没你高，没有看破这个“过分简化，回避瓶颈”的套，或者他知识有缺
: 陷，认为简化了也是mission
: impossible，或者他头脑发热感情用事。那你就不该同意。这样你自己显得尿一点，
: 但是赌局不开，古德霸ID就不会死。
: 3. 既然你接了，就该好好帮着古德霸。结果你撒手度假去了。完了古德霸苦巴巴的在
: 斑上央求人做case test，没人理。
: 4. 结果出了，古德霸立即执行了，你还在这里唧唧歪歪。
|
p*******r
发帖数: 123 | 65 谷德宝还是有点水平的， 只是自视过高加嘴臭， 这位跟班就是纯粹来搞笑的， 又没
水平， 翻来翻去句那几句话， 老子年轻， 老子门得傻。。
【在 s*******r 的大作中提到】
: 其实很简单，就是自以为是的人没赌品，输不起。
: 在我看来这帮输家比人赢家老魏还嚣张。
:
: mission
|
k******n
发帖数: 184 | 66
不否认你说得很有道理啊， 可我就是在乎看最后的代码来着， 我不在乎吵架结果谁输
谁赢啊， 如果是我一起工作的teammates或者朋友吵架我自然会往好的方面处理。论坛
上这点破事至于我费心尽力么？ 大家都隔着网络面子值几个钱？吵完就关机睡觉了，
就你把网络上这点破面子当回事了。
你们最后能看到代码还应该感谢我当catalyst让赌局事态升级， 看了代码如何实现的
到底是好东西还是水货每个人的看法不同， 但是比版面污了强多了。就事论事
我怎么处理这种事情IQ有个毛关系，我从来没觉得自己IQ咋了，很多技术和代码一样不
懂。 最后送你一句人患在好为人师， 版里删了很多聊天记录， 吐脏话的你肯定看不
到了。 别觉得看了部分context就能占领道德高地了， 我最恶心这一套。
【在 a*********a 的大作中提到】
: 看了一下你参赌的经过，觉得你做事很有问题。
: 1. 如果你目光犀利，判断准确，看出了魏过分简化，回避瓶颈，是个圈套，就应该明
: 确指出来，同时叫古不要赌。
: 2. 如果古水平没你高，没有看破这个“过分简化，回避瓶颈”的套，或者他知识有缺
: 陷，认为简化了也是mission
: impossible，或者他头脑发热感情用事。那你就不该同意。这样你自己显得尿一点，
: 但是赌局不开，古德霸ID就不会死。
: 3. 既然你接了，就该好好帮着古德霸。结果你撒手度假去了。完了古德霸苦巴巴的在
: 斑上央求人做case test，没人理。
: 4. 结果出了，古德霸立即执行了，你还在这里唧唧歪歪。
|
k******n
发帖数: 184 | 67
姓wei的跟班也就这个水平了， 门得傻也是回应你们头的狗嘴里吐不出象牙的脏话，
上下文都看不利索 LOL
【在 p*******r 的大作中提到】
: 谷德宝还是有点水平的， 只是自视过高加嘴臭， 这位跟班就是纯粹来搞笑的， 又没
: 水平， 翻来翻去句那几句话， 老子年轻， 老子门得傻。。
|
k******n
发帖数: 184 | 68
我赌之前就声明了我不赌任何东西， 包括自杀id这种事情。 最后我也认输了， 请问
什么叫做嚣张？
如果有一说一， 这事儿压根就不应该上赌约， 姓wei的提出赌约杀id的时候你们就应
当制止。 最后刻意设计一个赌局做了个toy，离最基本的LAMP web services都差远了
瓶颈全部刻意为了赢赌局， 自己做庄家又做裁判的赌局你们见过么？ 那时候你们在哪
？现在到来道貌岸然指责别人还有啥可说的？
我完全可以缩卵可以跟大流， 但事情前后还是说清楚的好， 杀档也没什么， 这里也
不是学习技术的好地方。
【在 s*******r 的大作中提到】
: 其实很简单，就是自以为是的人没赌品，输不起。
: 在我看来这帮输家比人赢家老魏还嚣张。
:
: mission
|
p*****y
发帖数: 529 | 69 你在哪儿认输了， 我怎么觉得你赢了呢？
【在 k******n 的大作中提到】
:
: 我赌之前就声明了我不赌任何东西， 包括自杀id这种事情。 最后我也认输了， 请问
: 什么叫做嚣张？
: 如果有一说一， 这事儿压根就不应该上赌约， 姓wei的提出赌约杀id的时候你们就应
: 当制止。 最后刻意设计一个赌局做了个toy，离最基本的LAMP web services都差远了
: 瓶颈全部刻意为了赢赌局， 自己做庄家又做裁判的赌局你们见过么？ 那时候你们在哪
: ？现在到来道貌岸然指责别人还有啥可说的？
: 我完全可以缩卵可以跟大流， 但事情前后还是说清楚的好， 杀档也没什么， 这里也
: 不是学习技术的好地方。
|
T********i
发帖数: 2416 | 70 说实话，这版上平均水平啥样我心里也有数。
你这种水平的，还真确实少见。几句话就看出来了。
【在 k******n 的大作中提到】
:
: 我赌之前就声明了我不赌任何东西， 包括自杀id这种事情。 最后我也认输了， 请问
: 什么叫做嚣张？
: 如果有一说一， 这事儿压根就不应该上赌约， 姓wei的提出赌约杀id的时候你们就应
: 当制止。 最后刻意设计一个赌局做了个toy，离最基本的LAMP web services都差远了
: 瓶颈全部刻意为了赢赌局， 自己做庄家又做裁判的赌局你们见过么？ 那时候你们在哪
: ？现在到来道貌岸然指责别人还有啥可说的？
: 我完全可以缩卵可以跟大流， 但事情前后还是说清楚的好， 杀档也没什么， 这里也
: 不是学习技术的好地方。
|
|
|
s*******r
发帖数: 310 | 71 认输以后说人家为了赢赌局刻意简化问题，很Low啥的，当时立赌约是你为啥不
challenge？还有这么认输的，这不是输不起是什么？嘲笑人家年纪大，吹自己年轻是
门萨普通会员，这不是嚣张是什么？别跟我提什么上下文，最近两天的对骂都是你那酸
不垃圾的认输文起的头。
【在 k******n 的大作中提到】
:
: 我赌之前就声明了我不赌任何东西， 包括自杀id这种事情。 最后我也认输了， 请问
: 什么叫做嚣张？
: 如果有一说一， 这事儿压根就不应该上赌约， 姓wei的提出赌约杀id的时候你们就应
: 当制止。 最后刻意设计一个赌局做了个toy，离最基本的LAMP web services都差远了
: 瓶颈全部刻意为了赢赌局， 自己做庄家又做裁判的赌局你们见过么？ 那时候你们在哪
: ？现在到来道貌岸然指责别人还有啥可说的？
: 我完全可以缩卵可以跟大流， 但事情前后还是说清楚的好， 杀档也没什么， 这里也
: 不是学习技术的好地方。
|
k******n
发帖数: 184 | 72
别人的不回， 就单独认真回你一段。
“ 认输以后说人家为了赢赌局刻意简化问题，很Low啥的，当时立赌约是你为啥不
我早说过接下赌约是为了让事情早点结束，我并不在乎输赢和自己的面子， 代码出来
大家就知道写了什么， 比过年之前每天被开新帖刷版事情毫无进展好太多。 然而事实
上赌约渺渺几行字是可以按照最坏原则解读的， 包括tests是否包含remote call这些
， 包括是否是一个完整的web services以及linear scalability到底算不算进去我统
统没有计较， 即使我知道。(但凡有些工作经验的都知道做软件外包合同如何详尽）
如果我真的需要使坏一开始不接即可，或者版里风向变了缩卵即可， 只是没想到我刻
意促进事态升级结束反倒被埋怨起来了。
“嘲笑人家年纪大，吹自己年轻是
这句话是回应姓wei的"你的智商都被狗吃了"的脏话， 如果你觉得我的回应很装逼这我
可以理解。我回复之后姓wei的如何回复你也可以看看， 我当然只有损几句他了。 如
果说之前的掐架中好虫一直嘴臭， 那么姓wei的嘴巴也少不了屎， 至于别的什么脏话
威胁的破事就不提了。你戴有色眼镜忽略这些很正常。
“别跟我提什么上下文，最近两天的对骂都是你那酸
我花了大概一个下午的时间读和确认源码，基本知道这些代码做了什么。每个人有自己
的解读， 我可以认输， 但这就是个单机toy, 还是跑在mem上用data structure模拟
db的玩具。 赌约的初衷至少应该是解决问题， 哪怕用虚拟机模拟一个node做db
server专门用来r/w我都不会说什么，这好歹也算模拟了一个bottole neck, 但是做的
这个东西纯粹是为了赢而设计的赌局完全违背了这个版存在的初衷以及骂架的中心点。
本来还指着业余看这版能学些经验谈，卷进个这个破事也真可笑的， 还真是劣币驱逐
良币， 什么赌约把在版上解答过很多技术问题的好虫赶跑了。
【在 s*******r 的大作中提到】
: 认输以后说人家为了赢赌局刻意简化问题，很Low啥的，当时立赌约是你为啥不
: challenge？还有这么认输的，这不是输不起是什么？嘲笑人家年纪大，吹自己年轻是
: 门萨普通会员，这不是嚣张是什么？别跟我提什么上下文，最近两天的对骂都是你那酸
: 不垃圾的认输文起的头。
|
s*******r
发帖数: 310 | 73 我也最后回你一贴，要么认赌服输闭嘴，要么就不要认输继续战斗，如果你仍然觉得自
己在理。古德霸如果只是认输自杀ID不要继续骂人阉党太监，形象会高大很多。另外，
老魏不该说智商被狗吃了这种话，但是你嘲笑别人年纪大，吹自己年轻是门萨会员啥的
真的更亮瞎别人狗眼，下次换个应对法，LOL。
【在 k******n 的大作中提到】
:
: 别人的不回， 就单独认真回你一段。
: “ 认输以后说人家为了赢赌局刻意简化问题，很Low啥的，当时立赌约是你为啥不
: 我早说过接下赌约是为了让事情早点结束，我并不在乎输赢和自己的面子， 代码出来
: 大家就知道写了什么， 比过年之前每天被开新帖刷版事情毫无进展好太多。 然而事实
: 上赌约渺渺几行字是可以按照最坏原则解读的， 包括tests是否包含remote call这些
: ， 包括是否是一个完整的web services以及linear scalability到底算不算进去我统
: 统没有计较， 即使我知道。(但凡有些工作经验的都知道做软件外包合同如何详尽）
: 如果我真的需要使坏一开始不接即可，或者版里风向变了缩卵即可， 只是没想到我刻
: 意促进事态升级结束反倒被埋怨起来了。
|
n*******7
发帖数: 181 | 74 这个楼歪得可以。让我们回到算法上来。
前面有人抱怨老魏code对存范围的二维数组的搜索是暴力解。我的理解是这是有
tradeoff的优化，针对小站数和大座位数，牺牲对站数的scalability，换得对座位数
的O(1). 对10站最多搜55次，取座时直接从stack上pop。如果没有这个二维数组，而
是对座位一个一个的搜，3000个座位，在座位大半满的情况下，要读多少次才能找到空
座或确定没有空座？那才是真正的暴力。
有可能当前这种算法不是最优。请大家想想有没有更好算法。 |
m*****k
发帖数: 731 | 75 没人说不要这个二维数组吧。
感谢提醒，站数n<=50比较实际。站数和座位数比起来确实小多了，即使n^2也赶不上，
直接从有限几个stack上pop，push应该比在O(n^2)个3000bit上置0置1快。
这就是请教讨论的目的，学习自己没想到的，开阔眼界，查漏补缺，绝没有抱怨之意。
感谢老姜，老魏，nanxiang7都来不及呢！
【在 n*******7 的大作中提到】
: 这个楼歪得可以。让我们回到算法上来。
: 前面有人抱怨老魏code对存范围的二维数组的搜索是暴力解。我的理解是这是有
: tradeoff的优化，针对小站数和大座位数，牺牲对站数的scalability，换得对座位数
: 的O(1). 对10站最多搜55次，取座时直接从stack上pop。如果没有这个二维数组，而
: 是对座位一个一个的搜，3000个座位，在座位大半满的情况下，要读多少次才能找到空
: 座或确定没有空座？那才是真正的暴力。
: 有可能当前这种算法不是最优。请大家想想有没有更好算法。
|
p*****y
发帖数: 529 | 76 是个爷们就shut up. 这点上好虫比你多了两balls。
【在 k******n 的大作中提到】
:
: 别人的不回， 就单独认真回你一段。
: “ 认输以后说人家为了赢赌局刻意简化问题，很Low啥的，当时立赌约是你为啥不
: 我早说过接下赌约是为了让事情早点结束，我并不在乎输赢和自己的面子， 代码出来
: 大家就知道写了什么， 比过年之前每天被开新帖刷版事情毫无进展好太多。 然而事实
: 上赌约渺渺几行字是可以按照最坏原则解读的， 包括tests是否包含remote call这些
: ， 包括是否是一个完整的web services以及linear scalability到底算不算进去我统
: 统没有计较， 即使我知道。(但凡有些工作经验的都知道做软件外包合同如何详尽）
: 如果我真的需要使坏一开始不接即可，或者版里风向变了缩卵即可， 只是没想到我刻
: 意促进事态升级结束反倒被埋怨起来了。
|
n*******7
发帖数: 181 | 77 是我不该用“抱怨”这个词。我自己也希望没有这个站数scalability的限制。
你太客气了。我也是在向你们学习中。
【在 m*****k 的大作中提到】
: 没人说不要这个二维数组吧。
: 感谢提醒，站数n<=50比较实际。站数和座位数比起来确实小多了，即使n^2也赶不上，
: 直接从有限几个stack上pop，push应该比在O(n^2)个3000bit上置0置1快。
: 这就是请教讨论的目的，学习自己没想到的，开阔眼界，查漏补缺，绝没有抱怨之意。
: 感谢老姜，老魏，nanxiang7都来不及呢！
|
n*******7
发帖数: 181 | 78 放假，终于有时间run GDB，才对老魏的程序有些理解了。仍然有些疑问。想向老魏和
大家请教。
先陈述一下基本的理解：
TrainTicketMap 是关键的数据库，表征对应车次当前所有空座. 它是一个二维数组，
两个indices分别是起始站和（站数 - 1). 它的值是一个stack（由单向链实现）。
stack上每一元素对应一个座位的站次间的空座范围，表示此座位从该起始站开始数该
站数范围内是空的。该元素的next指针指向stack上下一个对应不同座位的元素。
在初始状态，每个座位从起始站0开始10站都空，所以这个二维数组只在index［0，9］
有非空stack，里面压了对应所有座位的3000个元素，座位1在最上。假设第一个请求是
起始站3站数1，则座位1从站3到站4被出票，该座位空座范围［起始站，站数－1］从［
0，9］变为［0，2］和［4，5］。所以，对这个二维数组的操作（reserve函数里）是
：座位1在index［0，9］stack上的元素被free回TicketPool，从TicketPool重新
allocate两个元素给座位1，分别压进在index［0，2］和［4，5］的stacks。
整个操作分两步：allocate(); reserve().
allocate() 在TrainTicketMap找覆盖所请求站次的空座范围。搜索范围是顺着预先设
定的SearchOffsets，从小到大。所用时间较大而且不定，只读而不修改在
TrainTicketMap。是非transaction部分。
reserve() 是transaction部分，修改TrainTicketMap，用时很少并且固定。
请问，上述理解对吗？
我有几个问题：
1. 对站数能scale吗？如果站数从10变成100，TrainTicketMap与站数^2成正比，搜索
范围就增大100倍。allocate（）时间就增大100倍。当然可以用一个dedicated core
做reserve，把allocate分散到其它cores上。但如何同步就需要一些比较细碎的设计，
不如现在这样简洁了。另外，估计现有的core数很难消化得了100倍的计算量。所以，
对100站是不是就很难达到1M/s的指标了？
2. 如果朝实际方向再进一步，支持一个请求内多个座位连座，该怎么做？这应该是非
常贴近真实需要的。一家人一起走，座位应该是一起买，坐在一起的吧？如果顺着同样
的算法，TrainTicketMap是不是就该扩展成四维，多出的两维是起始座和座位数。那么
，搜索范围就扩大3000^2倍。这个算法是不是就不现实了？
3. 这个算法是源于成熟的理论，还是老魏或老姜的原创？无论如何，针对赌约的指标
要求，解决得非常精巧漂亮，令人佩服。这个问题，在逻辑上相当于在一个二维空间（
两轴分别是座位和站）不空的点上画叉叉，然后找可以容下长（连续座位数）宽（站数
）align在起始站的长方形的空域。这是不是另外还有更generic更好scale的理论和算
法？ |
T********i
发帖数: 2416 | 79 不敢当，我们可以讨论一下。
首先，这个算法是老姜原创。2年多以前他就贴出来过。很不幸立刻淹没在一大堆口水
帖中。这也证明了这个版根本不是严肃讨论技术的地方。我只不过在实现过程中做了一
些优化而已。这个事实我已经反复生命过，不敢掠人之美。
1。站数scalability肯定不好，算法本身很简单。站数从10变成100，allocate（）时
间就增大100倍。这个是肯定的。但是我们讨论的是火车票，不是汽车票。100站现实中
不可能。20站有没有可能我不知道。20站allocate()就要慢四倍。但是可以接受。
2。多个座位连坐的问题。这个倒是不用3000^2倍。其实如果把TrainTicketMap稍加改
变，座位不是stack而是bitmap的话，就会容易很多。搜索连坐估计可以做到O(m^2 ×
log(n))，m是站数，n是座位数；实际代价可以很小。
其实我现在的算法实现也很仓促。比如现在的TrainTicketMap是一个矩形，实际上只用
了一半，就是沿对角线的三角形而已。主要是我看指标远远超过了，就将就了。
事实上，这个算法很适合scale到外围机上去。这也是我故意分两步allocate和reserve
的原因。外围机通过allocate算法可以filter大量的无效请求。而且这个算法能够线性
分布到多核上面去。
至于复杂业务逻辑，可以选择在外围机或者核心机实现，或者both。
其实我认为，相对于算法，大家更应该思考架构的问题。不论业务逻辑复杂与否，这种
耦合问题究竟应该采用何种架构？当然考虑问题要全面，实现，维护，运营成本都要考
虑。简单逻辑你说不考虑公平和运营成本，把3000数据库当分布式计数器用。那么难道
稍微复杂的业务逻辑数据库就能够更优化？给我写一个query看看？ |
w********m
发帖数: 1137 | 80 个人觉得，魏老师的这个解决方案是一个高频交易的classic demo codebase。要进东
部银行的可以好好看看。
CPU比memory快10倍，memory比SSD快10倍，SSD比hard disk快10倍。hard disk比网线
快10倍。
魏老师告诉我们，高频交易最重要的是全内存运行，规避磁盘的IO限制。实现毫秒级的
transaction，一定要单机高并发。这是为什么东部银行喜欢折磨C＋＋的原因。
像12306这样的电商，瓶颈在磁盘和网线。DB建在磁盘上面，所以一定要选性能最好的
DB。 网线的堵塞没办法，只有靠买CDN来解决。电商大部分的钱都花在这方面了。
魏老师的性能再好，估计也不能改变磁盘和网线的物理限制。所以。。。 |
|
|
T********i
发帖数: 2416 | 81 其实吧，倒不如说该用啥就用啥。指望啥都有现成的，还要你干啥？
你现在，离磁盘和网线的物理限制还差的很远。大概有数量级的差别吧。比如，10G，
40G网卡现在大把。一台server装两块，就是20-80G。能服务多少12306并发用户？
我们谈架构，throughput是最重要的性能指标。所以我当年第一贴就说了，别的都是浮
云，只要拿出throughput就好了。比如我系统能持续多大的throughput，20G,40G,80G
？这事儿，和单机多机真的无关。
【在 w********m 的大作中提到】
: 个人觉得，魏老师的这个解决方案是一个高频交易的classic demo codebase。要进东
: 部银行的可以好好看看。
: CPU比memory快10倍，memory比SSD快10倍，SSD比hard disk快10倍。hard disk比网线
: 快10倍。
: 魏老师告诉我们，高频交易最重要的是全内存运行，规避磁盘的IO限制。实现毫秒级的
: transaction，一定要单机高并发。这是为什么东部银行喜欢折磨C＋＋的原因。
: 像12306这样的电商，瓶颈在磁盘和网线。DB建在磁盘上面，所以一定要选性能最好的
: DB。 网线的堵塞没办法，只有靠买CDN来解决。电商大部分的钱都花在这方面了。
: 魏老师的性能再好，估计也不能改变磁盘和网线的物理限制。所以。。。
|
r***6
发帖数: 401 | 82 Use bitmask makes great sense. If we assume at most 32 stations, then a
single uint32_t (unsigned) can represent one seat availability. A single
train seatmap is just an array of unsigned. Assume 4096 seats per train,
then the entire one train seatmap is only 16KB.
The reserve function would look like this:
unsigned _seatmap[NSEATS];
int Train::reserve(int start, int length)
{
//return seat index reserved, -1 if not available
unsigned mask = ((1 << length)-1) << start;
for (unsigned *seat = _seatmap; seat<_seatmap+NSEATS; ++seat) {
if (!(*seat & mask)) {
*seat |= mask;
return seat - _seatmap;
}
}
return -1;
}
This is essentially a linear search, but should be really fast because
almost all seat is within cache and access is linear. Each match is just a
32bit bitwise AND operation. |
m*p
发帖数: 1331 | 83 确实是hft里面经常看到的高性能单机版无io的东西。
【在 w********m 的大作中提到】
: 个人觉得，魏老师的这个解决方案是一个高频交易的classic demo codebase。要进东
: 部银行的可以好好看看。
: CPU比memory快10倍，memory比SSD快10倍，SSD比hard disk快10倍。hard disk比网线
: 快10倍。
: 魏老师告诉我们，高频交易最重要的是全内存运行，规避磁盘的IO限制。实现毫秒级的
: transaction，一定要单机高并发。这是为什么东部银行喜欢折磨C＋＋的原因。
: 像12306这样的电商，瓶颈在磁盘和网线。DB建在磁盘上面，所以一定要选性能最好的
: DB。 网线的堵塞没办法，只有靠买CDN来解决。电商大部分的钱都花在这方面了。
: 魏老师的性能再好，估计也不能改变磁盘和网线的物理限制。所以。。。
|
w********m
发帖数: 1137 | 84 单数据中心，运营商能给的稳定带宽能有100MB/s就不错了。每个新用户第一次登陆可
能就下载100KB，想象一下1000个用户同时浏览。
所以理想很丰满，现实总是很残酷。
80G
【在 T********i 的大作中提到】
: 其实吧，倒不如说该用啥就用啥。指望啥都有现成的，还要你干啥？
: 你现在，离磁盘和网线的物理限制还差的很远。大概有数量级的差别吧。比如，10G，
: 40G网卡现在大把。一台server装两块，就是20-80G。能服务多少12306并发用户？
: 我们谈架构，throughput是最重要的性能指标。所以我当年第一贴就说了，别的都是浮
: 云，只要拿出throughput就好了。比如我系统能持续多大的throughput，20G,40G,80G
: ？这事儿，和单机多机真的无关。
|
T********i
发帖数: 2416 | 85 实际情况比这个复杂一些。连座加上最小碎片检索可能需要先Or最多55种可能性，然后
再搜索。
AVX + prefetch每cycle处理512 bit是有可能的。
【在 r***6 的大作中提到】
: Use bitmask makes great sense. If we assume at most 32 stations, then a
: single uint32_t (unsigned) can represent one seat availability. A single
: train seatmap is just an array of unsigned. Assume 4096 seats per train,
: then the entire one train seatmap is only 16KB.
: The reserve function would look like this:
: unsigned _seatmap[NSEATS];
: int Train::reserve(int start, int length)
: {
: //return seat index reserved, -1 if not available
: unsigned mask = ((1 << length)-1) << start;
|
T********i
发帖数: 2416 | 86 你就别闹了。照你的算法，Google和好虫他们Netflix用户都可以吃屎去了。
【在 w********m 的大作中提到】
: 单数据中心，运营商能给的稳定带宽能有100MB/s就不错了。每个新用户第一次登陆可
: 能就下载100KB，想象一下1000个用户同时浏览。
: 所以理想很丰满，现实总是很残酷。
:
: 80G
|
n*******7
发帖数: 181 | 87 感谢老魏的详尽回答！老姜的算法和老魏的实现都做得很漂亮。很同意关于架构的论述。
对多票连座如何实现仍有不解。能否具体说说“把TrainTicketMap稍加改变，座位不是
stack而是bitmap”和“连座加上最小碎片检索可能需要先Or最多55种可能性”？
TrainTicketMap的index是［起始站，站数－1］。在［起始站，站数－1］的stack上的
非零值表示对某座这个站的范围（起始站－》起始站＋站数－1）是空的。改成bitmap
是不是bitmap里的1bits和stack上的元素有相同的含义？从同一个［起始站，站数－1
］点上找到的多个座位很可能是不相连的，而相连的座位可能在不同的［起始站，站数
－1］点上，怎样找？ |
n*******7
发帖数: 181 | 88 这个做法没有考虑每一站的seatmap都是不同的而且中途不换座。另外，这个函数没有
处理跨word边界的情况，当然，这是小问题。
【在 r***6 的大作中提到】
: Use bitmask makes great sense. If we assume at most 32 stations, then a
: single uint32_t (unsigned) can represent one seat availability. A single
: train seatmap is just an array of unsigned. Assume 4096 seats per train,
: then the entire one train seatmap is only 16KB.
: The reserve function would look like this:
: unsigned _seatmap[NSEATS];
: int Train::reserve(int start, int length)
: {
: //return seat index reserved, -1 if not available
: unsigned mask = ((1 << length)-1) << start;
|
r***6
发帖数: 401 | 89 There is no word boundary problem because at most 32 stations therefore a
32bit unsigned represents one seat availability throughout all stations.
As for adjacent seat issue, we can extend to 64(2 seats) or 128 bit(four
seats in a row) If no adjacent seats available you can also try to find
available seats with minimal distance after first scan.
Like teacher Wei said if you optimize for sse/avx, it is possible to check
512bits in a cycle, or 16 seats per cycle. For 4096 seats, you only need 256
cycles, approaching 85ns (at 3GHz) in worst case.
The key here is to minimize memory footprint to have sequential cache memory
access most of the time. This should be able to achieve an order of
magnitude performance. |
r***6
发帖数: 401 | 90 1. 中途换座 probably is not a requirement. If really in need, this probably
should be a ticket exchange or reissue.
2. Not sure if I understand "每一站的seatmap都是不同". My definition of one
seat bitmap word is vertical (availability throughout stations for one
particular seat) not horizontal (a snapshot of seat availability at
particular station) if you think entire train seat bitmap is a matrix, the
layout is column major indexes first. It is important because one bitwise
AND operation can check if this seat is a match for the trip riding mask.
这个做法没有考虑每一站的seatmap都是不同的而且中途不换座。另外，这个函数没有
处理跨word边界的情况，当然，这是小问题。
【在 n*******7 的大作中提到】
: 这个做法没有考虑每一站的seatmap都是不同的而且中途不换座。另外，这个函数没有
: 处理跨word边界的情况，当然，这是小问题。
|
|
|
T********i
发帖数: 2416 | 91 还是代码说话吧：
增加了一个函数： allocate2
其目的是，找到所有符合条件的座位空间，放到一个数组里。数组大小是座位数（3000）
剩下的，愿意怎么找相邻座位都简单了。至于优化也很简单，就是找sum(碎片）最小的
相邻座位。
注意，allocate和reserve可以优化到不同的core上做pipeline。也就是机行代码的事
情。
void TrainTicketMap::allocate2(int start, int length, Ticket **seats) {
length--; // normalize to [0, 9]
for (Offsets::iterator it = offsets.begin(); it != offsets.end(); ++it) {
register int curStart = start + it->start;
register int curLength = length - it->start + it->length;
if (curStart >= 0 && curLength < SEGMENTS) {
//printf("Searching %d %d\n", curStart, curLength);
size_t index = curStart + curLength * SEGMENTS;
Ticket *cur = _map[index];
while (cur) {
seats[cur->_seat] = cur;
cur = cur->_next;
}
}
}
}
这个allocate2性能如何呢？
下面的代码基本上是worst case，每次都会收集满3000座位，而且促进最大cache miss。
static void benchmark() {
double t1 = getTime();
printf("start benchmark\n");
Ticket *seats[SEATS];
for (size_t i=0; i<10000000LL; i++) {
int train = rand() % TRAINS;
int start = rand() % SEGMENTS;
int length = rand() % (SEGMENTS - start);
if (length == 0) {
length = 1;
}
memset(seats, 0, sizeof(Ticket *) * SEATS);
trains[train]->allocate2(start, length, seats);
}
double t2 = getTime();
printf("Total time = %f\n", t2 - t1);
}
结果：1000万张票大约34秒。
所以如果支持无限连座，worst case大约30万票/s。Best case可以多核并行，仍然能
超过1000万。
注意，allocate2仍然能够无限scalable。所以查询的throughput基本是无限的。 |
n*******7
发帖数: 181 | 92 My bad. I misunderstood seatmap as one bit per seat. You actually mean one
bit per station.
So, it is just scanning the array of seats with complexity of O(seats).
TrainTicketsMap is not used. Right?
256
memory
【在 r***6 的大作中提到】
: There is no word boundary problem because at most 32 stations therefore a
: 32bit unsigned represents one seat availability throughout all stations.
: As for adjacent seat issue, we can extend to 64(2 seats) or 128 bit(four
: seats in a row) If no adjacent seats available you can also try to find
: available seats with minimal distance after first scan.
: Like teacher Wei said if you optimize for sse/avx, it is possible to check
: 512bits in a cycle, or 16 seats per cycle. For 4096 seats, you only need 256
: cycles, approaching 85ns (at 3GHz) in worst case.
: The key here is to minimize memory footprint to have sequential cache memory
: access most of the time. This should be able to achieve an order of
|
n*******7
发帖数: 181 | 93 谢谢老魏！确实用代码说话是最清楚的。：）
理解你的做法了。每次memset清空seat数组，找出所有的范围，排出所有seats，然后
找连座和优化碎片就容易了。我没往这个方向想是因为以为这样会慢(O(n) complexity
)，现在看你的benchmark确实performance也还不错。
多谢多谢！
3000）
) {
【在 T********i 的大作中提到】
: 还是代码说话吧：
: 增加了一个函数： allocate2
: 其目的是，找到所有符合条件的座位空间，放到一个数组里。数组大小是座位数（3000）
: 剩下的，愿意怎么找相邻座位都简单了。至于优化也很简单，就是找sum(碎片）最小的
: 相邻座位。
: 注意，allocate和reserve可以优化到不同的core上做pipeline。也就是机行代码的事
: 情。
: void TrainTicketMap::allocate2(int start, int length, Ticket **seats) {
: length--; // normalize to [0, 9]
: for (Offsets::iterator it = offsets.begin(); it != offsets.end(); ++it) {
|
T********i
发帖数: 2416 | 94 其实还有很多可以讨论的。比如，复杂搜索例如连座之类，是否放在外围机比较好？这
样，核心机出票保证>1000万/s没有问题。
还有，我开始确实考虑每个座位block用bitmap，这样3000要375 bytes。当然OR操作要
用AVX加速。memory带宽需求显著增加，但是实际上不见得比我的allocate2慢。当然需
要实际测才知道。
至于3000数据库并行，我还真希望qxc写个query出来，别的不说，先把单张票优化一下
给我看看？
另外，这个worst case实际上是不会发生的。即使10%请求都是连座的，性能依然远超
1M/s。
至于12306用的gemfire内存数据库，gemfire还是靠Bear Stearns发家的。那时期我还
在Bear Stearns prop desk做Associate Director。具体情况我还是比较了解的。我不
认为gemfire在系统中能够起到任何关键作用。 |
n*******7
发帖数: 181 | 95 reserve() 是应该在一个dedicated的core上以保证速度。复杂搜索可以offload到其它
cores上。你说的外围机是这些cores，还是真正的机子？如果是真正的机子，memory不
在一个系统内，还需要一些message queue的设计吧？
bitmap有可能更快。既然支持AVX，memory带宽应该够吧。
12306的瓶颈估计还是在IO，而不是这些内存操作。
我还有一个不清楚的地方，就是如何处理退票。如果付款出错，就需要把票返回到
TrainTicketsMap里，另外还需要合并原来被此票分裂的范围。这是不是也对称地分两
步，先搜索被此票分裂的范围，再进transaction写进map里？
【在 T********i 的大作中提到】
: 其实还有很多可以讨论的。比如，复杂搜索例如连座之类，是否放在外围机比较好？这
: 样，核心机出票保证>1000万/s没有问题。
: 还有，我开始确实考虑每个座位block用bitmap，这样3000要375 bytes。当然OR操作要
: 用AVX加速。memory带宽需求显著增加，但是实际上不见得比我的allocate2慢。当然需
: 要实际测才知道。
: 至于3000数据库并行，我还真希望qxc写个query出来，别的不说，先把单张票优化一下
: 给我看看？
: 另外，这个worst case实际上是不会发生的。即使10%请求都是连座的，性能依然远超
: 1M/s。
: 至于12306用的gemfire内存数据库，gemfire还是靠Bear Stearns发家的。那时期我还
|
T********i
发帖数: 2416 | 96 单机内，不相关搜索可以offload到多核，所以实际性能应该远远超过1M/s。除非像
goodbug和zhaoce那样专门选最恶劣的sequence来测试。
外围机是真正的机子，本来就需要message queue设计，这个我说过多次了，机制和hot
standby recovery一样。其实，设计中，任何外围机都能当hot standby使用的。
这种load，多机间multicast sync状态基本能够达到latency微秒级别。
退票反正也不多。是一个worst case O(SEATS)的过程。实际性能最差应该在单核每秒
20万-30万票。平均应该远超。
【在 n*******7 的大作中提到】
: reserve() 是应该在一个dedicated的core上以保证速度。复杂搜索可以offload到其它
: cores上。你说的外围机是这些cores，还是真正的机子？如果是真正的机子，memory不
: 在一个系统内，还需要一些message queue的设计吧？
: bitmap有可能更快。既然支持AVX，memory带宽应该够吧。
: 12306的瓶颈估计还是在IO，而不是这些内存操作。
: 我还有一个不清楚的地方，就是如何处理退票。如果付款出错，就需要把票返回到
: TrainTicketsMap里，另外还需要合并原来被此票分裂的范围。这是不是也对称地分两
: 步，先搜索被此票分裂的范围，再进transaction写进map里？
|
n*******7
发帖数: 181 | 97 懂了，多谢！
多机间multicast sync状态真能达到latency微秒级别吗？throughput是没问题的。但
是，就单个ticket的latency来说，上下两边的protocal stack就要花不少时间吧，再
加上处理message queue的延迟(到queue里也不一定能马上处理），能压缩到微秒级
吗？我没实际测过，不知道。能否说说在实际HFT系统里的message，除去网络的
延迟，在机子里传递过程需要多少时间？
hot
【在 T********i 的大作中提到】
: 单机内，不相关搜索可以offload到多核，所以实际性能应该远远超过1M/s。除非像
: goodbug和zhaoce那样专门选最恶劣的sequence来测试。
: 外围机是真正的机子，本来就需要message queue设计，这个我说过多次了，机制和hot
: standby recovery一样。其实，设计中，任何外围机都能当hot standby使用的。
: 这种load，多机间multicast sync状态基本能够达到latency微秒级别。
: 退票反正也不多。是一个worst case O(SEATS)的过程。实际性能最差应该在单核每秒
: 20万-30万票。平均应该远超。
|
T********i
发帖数: 2416 | 98 上kernel bypass的10G网卡。我的一个系统，如果进来的market data tick恰好
trigger一个order，用corvil分光测wire-to-wire的速度（half round trip），
median在10us以内，最大的outlier也在20us以内。
实测ping-pong，median 5us左右吧。
我们这种load，latency控制在20us以内没问题。
注意，我现在的实现，针对1G网卡的throughput做了些优化。比如尽量pool输出到一个
MTU以上(1400 bytes)。如果用10G网卡，可以用不同的优化方案。
【在 n*******7 的大作中提到】
: 懂了，多谢！
: 多机间multicast sync状态真能达到latency微秒级别吗？throughput是没问题的。但
: 是，就单个ticket的latency来说，上下两边的protocal stack就要花不少时间吧，再
: 加上处理message queue的延迟(到queue里也不一定能马上处理），能压缩到微秒级
: 吗？我没实际测过，不知道。能否说说在实际HFT系统里的message，除去网络的
: 延迟，在机子里传递过程需要多少时间？
:
: hot
|
n*******7
发帖数: 181 | 99 很有用的数据，谢谢！希望这里多些这样实用的信息，比吵架有意义多了。:)
优化到这个数量级差不多是到头了。在这点时间里跑不了多少business logic。 |
y*****r
发帖数: 327 | |
|
|
T********i
发帖数: 2416 | 101 我用了很多年solarflare。这个pc12306还真没上solarflare。性能足够了。
【在 y*****r 的大作中提到】
: 这是上了solarflare以后的数据？
|
y*****r
发帖数: 327 | 102 谢谢回答，我是说你5-20微秒的测试是不是solarflare/openonload 之后的数据。
【在 T********i 的大作中提到】
: 我用了很多年solarflare。这个pc12306还真没上solarflare。性能足够了。
|
T********i
发帖数: 2416 | 103 是。Solarflare卖这么贵就是因为latency低。
【在 y*****r 的大作中提到】
: 谢谢回答，我是说你5-20微秒的测试是不是solarflare/openonload 之后的数据。
|
y*****r
发帖数: 327 | 104 从send（）到wire大概多少延时？谢谢。
【在 T********i 的大作中提到】
: 是。Solarflare卖这么贵就是因为latency低。
|
T********i
发帖数: 2416 | 105 3-5us吧。
【在 y*****r 的大作中提到】
: 从send（）到wire大概多少延时？谢谢。
|
n*******7
发帖数: 181 | 106 这3-5us是不是主要在加每层header,每加一层要把payload memcpy一下？
如果追究一下极限，在两个直接连接的机子上，用proprietary protocol，不用支持通
常的protocol，所以不用一层层加header，网卡直接DMA数据到cache里，不知道这样的
物理极限是多少。
【在 T********i 的大作中提到】
: 3-5us吧。
|
y*****r
发帖数: 327 | 107 但前面说ping pong 是5微秒？
【在 T********i 的大作中提到】
: 3-5us吧。
|
T********i
发帖数: 2416 | 108 极限就是PCI-E Latency。Solarflare号称half round trip最低3.X us。根据我的经验
偶尔能够达到。当然我多少有点business logic在里面。
infiniband latency更低，但是没有轮子用它。
【在 n*******7 的大作中提到】
: 这3-5us是不是主要在加每层header,每加一层要把payload memcpy一下？
: 如果追究一下极限，在两个直接连接的机子上，用proprietary protocol，不用支持通
: 常的protocol，所以不用一层层加header，网卡直接DMA数据到cache里，不知道这样的
: 物理极限是多少。
|
T********i
发帖数: 2416 | 109 half round trip.
【在 y*****r 的大作中提到】
: 但前面说ping pong 是5微秒？
|
m*****k
发帖数: 731 | 110 :假设第一个请求是
:起始站3站数1，则座位1从站3到站4被出票，该座位空座范围［起始站，站数－1］从［
:0，9］变为［0，2］和［4，5］。
为啥不是 ［0，3］和［4，5］?
:它是一个二维数组，
这样有何妙处啊？ |
|
|
n*******7
发帖数: 181 | 111 我曾经测过PCIe latency. 用CPU back to back读写PCIe device 同一个32-bit
register, 每次需要500ns。你看到3-5us时你的packet有多少bytes？不知道是
不是同一个cacheline的数据都能在同一个500ns里完成，不然很难解释一个packet
（假设64 bytes）能在几个us内完成。
【在 T********i 的大作中提到】
: 极限就是PCI-E Latency。Solarflare号称half round trip最低3.X us。根据我的经验
: 偶尔能够达到。当然我多少有点business logic在里面。
: infiniband latency更低，但是没有轮子用它。
|
n*******7
发帖数: 181 | 112 站数是3，站数－1是2， 所以是［0，2］
就是个记录空座范围的方式，在stack 里O(1)找到空座。
从［ |
m*****k
发帖数: 731 | 113 多谢回复，
用个例子来说吧，
假如只有一次车，从北京到广州，共4站，
s0(北京)， s1(天津)， s2(上海)， s3(广州)，s表示station
车上只有两个座位： seat1, seat2
初始状态：
arr[0,0] 表示s0 到 s1的空座位集合，空Stack
...
arr[0,1] 表示s0 到 s2的空座位集合，空Stack
...
arr[0,2] 表示s0 到 s3的空座位集合，a Stack { seat1 , seat2}，
...
没出票时，只有arr[0,2] 有非空值 { seat1 , seat2}，
我的理解对吗？
站数是3，站数－1是2， 所以是［0，2］
就是个记录空座范围的方式，在stack 里O(1)找到空座。
从［
【在 n*******7 的大作中提到】
: 站数是3，站数－1是2， 所以是［0，2］
: 就是个记录空座范围的方式，在stack 里O(1)找到空座。
: 从［
|
n*******7
发帖数: 181 | 114 你的理解是对的。
code中的变量名ticket有点misleading。这其实是某座在站之间的空座范围。这个数组
＋stack存着所有范围。如果有一个空座，它必然在某个范围之内。所有范围的集合表
征所有空座。数组是这些范围的存储和索引方式。
【在 m*****k 的大作中提到】
: 多谢回复，
: 用个例子来说吧，
: 假如只有一次车，从北京到广州，共4站，
: s0(北京)， s1(天津)， s2(上海)， s3(广州)，s表示station
: 车上只有两个座位： seat1, seat2
: 初始状态：
: arr[0,0] 表示s0 到 s1的空座位集合，空Stack
: ...
: arr[0,1] 表示s0 到 s2的空座位集合，空Stack
: ...
|
m*****k
发帖数: 731 | 115 那为啥用这种索引方法呢？
arr[i,j] i 和 j 表示不同东西，其妙处何在？
就我举的例子而言，如果第一个请求是出一张从s1到s2的票，
这个算法是如何迅速找到arr[0,2] 中的seat1的呢？
arr[1,0]是空栈啊。
为啥不用
arr[i，j]表示从si到sj的空座集合呢？
从没用过cpp，看不懂老魏的代码，恳求好心人能精辟的指点一下，毕竟算法是不需要
用特定language来解释的。
【在 n*******7 的大作中提到】
: 你的理解是对的。
: code中的变量名ticket有点misleading。这其实是某座在站之间的空座范围。这个数组
: ＋stack存着所有范围。如果有一个空座，它必然在某个范围之内。所有范围的集合表
: 征所有空座。数组是这些范围的存储和索引方式。
|
T********i
发帖数: 2416 | 116 最少56bytes, 最多1500bytes。
inbound UDP, outbound TCP。
其实Intel有trick。你搜一下Intel Data Direct I/O。直接PCI- E到LLC(Last level
cache)。甚至一个memory读写都不需要。
读一下Intel的白皮书。这些年各种花样层出不穷。这也是延续摩尔定律的一种方式。
其实，这才是新玩意儿。比起来分布式才是上个世纪的。这些东西的玩法，5年前都不
可能。
【在 n*******7 的大作中提到】
: 我曾经测过PCIe latency. 用CPU back to back读写PCIe device 同一个32-bit
: register, 每次需要500ns。你看到3-5us时你的packet有多少bytes？不知道是
: 不是同一个cacheline的数据都能在同一个500ns里完成，不然很难解释一个packet
: （假设64 bytes）能在几个us内完成。
|
m*****k
发帖数: 731 | 117 可以请教一下魏老师和老姜为啥用［起始站号，站数 - 1］来做index呢？
如果arr[i,j] 存所有座位的bitmap，i，j是起始，终止站号，查询空座位不是O(1)么？
×
【在 T********i 的大作中提到】
: 不敢当，我们可以讨论一下。
: 首先，这个算法是老姜原创。2年多以前他就贴出来过。很不幸立刻淹没在一大堆口水
: 帖中。这也证明了这个版根本不是严肃讨论技术的地方。我只不过在实现过程中做了一
: 些优化而已。这个事实我已经反复生命过，不敢掠人之美。
: 1。站数scalability肯定不好，算法本身很简单。站数从10变成100，allocate（）时
: 间就增大100倍。这个是肯定的。但是我们讨论的是火车票，不是汽车票。100站现实中
: 不可能。20站有没有可能我不知道。20站allocate()就要慢四倍。但是可以接受。
: 2。多个座位连坐的问题。这个倒是不用3000^2倍。其实如果把TrainTicketMap稍加改
: 变，座位不是stack而是bitmap的话，就会容易很多。搜索连坐估计可以做到O(m^2 ×
: log(n))，m是站数，n是座位数；实际代价可以很小。
|
n*******7
发帖数: 181 | 118 这个问题老魏可能有更好回答。就我的理解，“arr[i，j]表示从si到sj的空座集合”
也完全可以。
［上车站，站数］和［上车站，下车站］是一一对应，完全等效的。我看不出有什么
tradeoff。
在TrainTicketMap::allocate（）里，用Offsets iterator遍历所有可能范围。其实这
里如果不用
C++的iterator遍历固定的SearchPatterns，直接用C的办法对两个indices用两层for
loop，
loop的range可变，还可以跳过一些entry，省了if (curStart >= 0 && curLength <
SEGMENTS)，
会更快一些。老魏估计是因为足够快就不讲究了。 |
m*****k
发帖数: 731 | 119 多谢nanxiang7！
我就是觉得虽然实际上等效但为何要多余算一下站数-1，故而好奇老姜和老魏为何选这
个.
谢谢你confirm了查询是brute force,我可以好好睡觉了，:-p
【在 n*******7 的大作中提到】
: 这个问题老魏可能有更好回答。就我的理解，“arr[i，j]表示从si到sj的空座集合”
: 也完全可以。
: ［上车站，站数］和［上车站，下车站］是一一对应，完全等效的。我看不出有什么
: tradeoff。
: 在TrainTicketMap::allocate（）里，用Offsets iterator遍历所有可能范围。其实这
: 里如果不用
: C++的iterator遍历固定的SearchPatterns，直接用C的办法对两个indices用两层for
: loop，
: loop的range可变，还可以跳过一些entry，省了if (curStart >= 0 && curLength <
: SEGMENTS)，
|
z****e
发帖数: 54598 | 120
这个算法有啥难看懂的？
基本上都是暴力解
其实就是一个简单的计数器
早就说了，一旦分布并发遇到了困难
的就回去用单机
这是老魏的解法的唯一思路
蠢不可及
【在 m*****k 的大作中提到】
: 多谢nanxiang7！
: 我就是觉得虽然实际上等效但为何要多余算一下站数-1，故而好奇老姜和老魏为何选这
: 个.
: 谢谢你confirm了查询是brute force,我可以好好睡觉了，:-p
|
|
|
n*******7
发帖数: 181 | 121 按你的表达法，如果座0在站3到站5间有空，arr[3,5] 的bit0是1，arr[3,4］和arr[4,
5]的bit0 是1吗？
老魏的做法，在查询的时候需要看多个点，在出票的时候（transaction）只需要变一
到三个。如果
你查询时是O（1），在出票时需要改写多少地方？
么？
【在 m*****k 的大作中提到】
: 可以请教一下魏老师和老姜为啥用［起始站号，站数 - 1］来做index呢？
: 如果arr[i,j] 存所有座位的bitmap，i，j是起始，终止站号，查询空座位不是O(1)么？
:
: ×
|
n*******7
发帖数: 181 | 122 至少在这个问题上，不是因为分布并发遇到了困难就回去用单机，而是针对这个问题本
身的scale在设计合理把transaction精简后单机完全可以胜任。
当然分布有很多高深的技术。但对赌约的指标老魏的code不是完全解决了问题吗？
【在 z****e 的大作中提到】
:
: 这个算法有啥难看懂的？
: 基本上都是暴力解
: 其实就是一个简单的计数器
: 早就说了，一旦分布并发遇到了困难
: 的就回去用单机
: 这是老魏的解法的唯一思路
: 蠢不可及
|
n*******7
发帖数: 181 | 123 我知道有这个trick，可以省CPU读packet 的时间。但就单个packet的latency来说，把
数据从wire上运
到LLC里，还是要花时间的，不知道占了3-5us中多大的部分。
level
【在 T********i 的大作中提到】
: 最少56bytes, 最多1500bytes。
: inbound UDP, outbound TCP。
: 其实Intel有trick。你搜一下Intel Data Direct I/O。直接PCI- E到LLC(Last level
: cache)。甚至一个memory读写都不需要。
: 读一下Intel的白皮书。这些年各种花样层出不穷。这也是延续摩尔定律的一种方式。
: 其实，这才是新玩意儿。比起来分布式才是上个世纪的。这些东西的玩法，5年前都不
: 可能。
|
w**z
发帖数: 8232 | 124 对于互联网的应用，追求us 级别的优化真的让人无语。
【在 n*******7 的大作中提到】
: 我知道有这个trick，可以省CPU读packet 的时间。但就单个packet的latency来说，把
: 数据从wire上运
: 到LLC里，还是要花时间的，不知道占了3-5us中多大的部分。
:
: level
|
z****e
发帖数: 54598 | 125 txn哪里精简了？
把一个从买票订票到最后金钱划账简化成一个内存中的int赋值操作
你见过哪个txn是原子操作的？
如果都是原子操作，还要txn干什么？
话说你啥时候见过金钱交易是简单的int的赋值操作？
这不是遇到困难就回去用单机是什么？
【在 n*******7 的大作中提到】
: 至少在这个问题上，不是因为分布并发遇到了困难就回去用单机，而是针对这个问题本
: 身的scale在设计合理把transaction精简后单机完全可以胜任。
: 当然分布有很多高深的技术。但对赌约的指标老魏的code不是完全解决了问题吗？
|
z****e
发帖数: 54598 | 126
对于大多数互联网的金钱交易来说
最大的latency来自pc到网站，或者说来自公网的路由器上的迟滞
这是一
其次，对于互联网的金钱交易来说
第二大的latency来自你系统本身跟merchant还有acquirer也就是银行等金钱存放系统
的io
因为这两步都需要经过公网，而且可能是跨地域操作
这里面的latency绝对是ms级的，甚至10，100ms级的
你在这个时候拼命优化一台单机的效率，4 what？
你有这个功夫，把路由好好优化一下，兴许更快
而且对于这种交易来说，txn往往是涉及到多个不同系统之间的协调
如果只是内存中的原子操作，还做个屁啊
要你做？
就好比人家要你做台汽车
你举了个轮子一路滚过去
因为汽车也用了轮子
这叫汽车？
老魏的解决方案解决了毛问题
从一开始的单机到最后拼命在外围机加机器
同时拼命简化需求，还有这样的？
现实中做系统，ba提了一个需求，你说，这个太麻烦
这不做，那不做，我就做最简单的i++
那你说ba会怎么办？第二天你就卷铺盖滚蛋了
【在 n*******7 的大作中提到】
: 至少在这个问题上，不是因为分布并发遇到了困难就回去用单机，而是针对这个问题本
: 身的scale在设计合理把transaction精简后单机完全可以胜任。
: 当然分布有很多高深的技术。但对赌约的指标老魏的code不是完全解决了问题吗？
|
z****e
发帖数: 54598 | 127
第一个，12306的票的数据肯定不在内存中
你想过如何从不同的分布式db中读取你需要的数据么？
老魏的想法很简单，就是直接从local disk上读出来
你觉得这个现实么？
就这么一个简单的需求，就搞死你了，别谈后面的了
说到底就是一个单机计数器
因为计数器这不管那不管，只管i++
这个你要有兴趣，自己做一个for loop，然后测一下各个硬件的能够爬到的最高i
就这种了，有个鸟现实意义
之所以写软件，就是要有创造，就是要解决实际问题
而不是回避问题，老魏的所谓解决方案，就看他在不停滴躲避各种问题
最后自己都承认不是12306，是一个计数器了
现在还打算翻案咯？
我靠，如果谁敢继续说这个是12306的话，我就要发毒誓了
别自找没趣哦
【在 n*******7 的大作中提到】
: 放假，终于有时间run GDB，才对老魏的程序有些理解了。仍然有些疑问。想向老魏和
: 大家请教。
: 先陈述一下基本的理解：
: TrainTicketMap 是关键的数据库，表征对应车次当前所有空座. 它是一个二维数组，
: 两个indices分别是起始站和（站数 - 1). 它的值是一个stack（由单向链实现）。
: stack上每一元素对应一个座位的站次间的空座范围，表示此座位从该起始站开始数该
: 站数范围内是空的。该元素的next指针指向stack上下一个对应不同座位的元素。
: 在初始状态，每个座位从起始站0开始10站都空，所以这个二维数组只在index［0，9］
: 有非空stack，里面压了对应所有座位的3000个元素，座位1在最上。假设第一个请求是
: 起始站3站数1，则座位1从站3到站4被出票，该座位空座范围［起始站，站数－1］从［
|
a*********a
发帖数: 3656 | 128 今天什么意思，赵老给古总的专场追悼会？版主刚打扫完上一场集体追悼会的会场。
【在 z****e 的大作中提到】
:
: 第一个，12306的票的数据肯定不在内存中
: 你想过如何从不同的分布式db中读取你需要的数据么？
: 老魏的想法很简单，就是直接从local disk上读出来
: 你觉得这个现实么？
: 就这么一个简单的需求，就搞死你了，别谈后面的了
: 说到底就是一个单机计数器
: 因为计数器这不管那不管，只管i++
: 这个你要有兴趣，自己做一个for loop，然后测一下各个硬件的能够爬到的最高i
: 就这种了，有个鸟现实意义
|
T********i
发帖数: 2416 | 129 Intel DDIO paper号称data rate是250G。我估计有Initial fixed latency，我猜测有
1us左右。
【在 n*******7 的大作中提到】
: 我知道有这个trick，可以省CPU读packet 的时间。但就单个packet的latency来说，把
: 数据从wire上运
: 到LLC里，还是要花时间的，不知道占了3-5us中多大的部分。
:
: level
|
k******n
发帖数: 184 | 130
你这几个三番五次提的最关键最难解决的问题什么时候他们正面回答过了？
度个假回来看版里这气氛以为做出了什么惊天动地的solution把好虫打得心服口服，
说到底就是为自己面子设计赌约， 简化一切条件，做了个toy, 还真是劣币驱逐良币。
人目的是赢赌约啊， 不是做出什么东西解决问题， 我也认输罢了。
另外姓wei的当时是要3个人都接赌约的， 第三个人可是claim 这在单机版要能linear
scalability的， 这个单机版的toy硬件再怎么多核也linear scale不了。不过要是不
算进赌约也无妨， 反正我已经认输。
【在 z****e 的大作中提到】
:
: 第一个，12306的票的数据肯定不在内存中
: 你想过如何从不同的分布式db中读取你需要的数据么？
: 老魏的想法很简单，就是直接从local disk上读出来
: 你觉得这个现实么？
: 就这么一个简单的需求，就搞死你了，别谈后面的了
: 说到底就是一个单机计数器
: 因为计数器这不管那不管，只管i++
: 这个你要有兴趣，自己做一个for loop，然后测一下各个硬件的能够爬到的最高i
: 就这种了，有个鸟现实意义
|
|
|
z****e
发帖数: 54598 | 131
linear
对啊，本来来这里也就是看看各个硅谷公司大概用了什么技术
能够取长补短一下，看看如何解决问题
结果麻痹的，被一堆卖机器的给搞得乌烟瘴气的
一天到晚就是做点简单的计数器
真是恶心啊，还tmd说别人是娼
摆明了自己就是一娼嘛，说的都是上个世纪的过时的破烂
还非要跟人家打赌，搞得好像自己的东西宇宙第一一样
要真有那个本事，那就去竞标啊，去fb演讲啊
就像vert.x和netty的某个德国作者一样，去fb分享经验啊
麻痹的又没这个本事，那不行，去12306竞标也行啊
结果也不行，连电商都搞不出来，做了半死一个计数器
愚人愚己罢了，本来这些卖机器的老年人写的帖子就没几个人爱看
如果不是哗众取宠一番，估计大多数人都直接忽略了
非要到处恶心人，真是人至贱则无敌
【在 k******n 的大作中提到】
:
: 你这几个三番五次提的最关键最难解决的问题什么时候他们正面回答过了？
: 度个假回来看版里这气氛以为做出了什么惊天动地的solution把好虫打得心服口服，
: 说到底就是为自己面子设计赌约， 简化一切条件，做了个toy, 还真是劣币驱逐良币。
: 人目的是赢赌约啊， 不是做出什么东西解决问题， 我也认输罢了。
: 另外姓wei的当时是要3个人都接赌约的， 第三个人可是claim 这在单机版要能linear
: scalability的， 这个单机版的toy硬件再怎么多核也linear scale不了。不过要是不
: 算进赌约也无妨， 反正我已经认输。
|
k******n
发帖数: 184 | 132
我注册mitbbs本来也不久， 不喜欢别的版块乌烟瘴气刚进来以为找到了一片净土想好
好学习， 结果被姓wei的发言震惊了。还有几个捣乱唯恐天下不乱的id。
他们卖不卖机器我不知道，人品如何我也不提， 我只是觉得为了赢赌局而刻意简化条
件回避web services的瓶颈这样的初衷太low， 相反我宁愿输钱输面子也想学点新东西
。事实上看懂算法后其实我有办法压缩状态把姓wei的内存优化一截，不过我不想参加
和这个话题有关的任何事情了， 谁让我们打工的就是不如自由创业者任性。
还有件事情很奇怪， 我刚进本版没人认识我， 我也从来没说过我学校在FB或者能挣钱
怎么怎么样，好虫也从没倚仗过netflix， 但是在争论的时候总三番五次被对方提起公
司学校挣多少啥的，这一点我还真是费解，有理说理， 你主动提这个什么意思？ 更别
说那些威胁告hr的弱智行径了。
【在 z****e 的大作中提到】
:
: linear
: 对啊，本来来这里也就是看看各个硅谷公司大概用了什么技术
: 能够取长补短一下，看看如何解决问题
: 结果麻痹的，被一堆卖机器的给搞得乌烟瘴气的
: 一天到晚就是做点简单的计数器
: 真是恶心啊，还tmd说别人是娼
: 摆明了自己就是一娼嘛，说的都是上个世纪的过时的破烂
: 还非要跟人家打赌，搞得好像自己的东西宇宙第一一样
: 要真有那个本事，那就去竞标啊，去fb演讲啊
|
a*********a
发帖数: 3656 | 133 你的意思是，一个里里外外吵了两年年的问题，古德霸还被魏耍了？魏“刻意简化，回
避瓶颈”，射了个套，古德霸还直接就钻了？
这是贬低古德霸的智商呢，还是贬低古德霸的情商呢？
相反我宁愿输钱输面子也想学点新东西
【在 k******n 的大作中提到】
:
: 我注册mitbbs本来也不久， 不喜欢别的版块乌烟瘴气刚进来以为找到了一片净土想好
: 好学习， 结果被姓wei的发言震惊了。还有几个捣乱唯恐天下不乱的id。
: 他们卖不卖机器我不知道，人品如何我也不提， 我只是觉得为了赢赌局而刻意简化条
: 件回避web services的瓶颈这样的初衷太low， 相反我宁愿输钱输面子也想学点新东西
: 。事实上看懂算法后其实我有办法压缩状态把姓wei的内存优化一截，不过我不想参加
: 和这个话题有关的任何事情了， 谁让我们打工的就是不如自由创业者任性。
: 还有件事情很奇怪， 我刚进本版没人认识我， 我也从来没说过我学校在FB或者能挣钱
: 怎么怎么样，好虫也从没倚仗过netflix， 但是在争论的时候总三番五次被对方提起公
: 司学校挣多少啥的，这一点我还真是费解，有理说理， 你主动提这个什么意思？ 更别
|
k******n
发帖数: 184 | 134
还两年， 我刚进来几个星期看着那套做派都烦了， 这么吵下去威胁互相问候的整个版
都给污了， 你打人家脸人家不回重新开一个往复循环自说自话。 我的目的很简单，整
个topic赶紧结束所有人shut up最好。
接这赌约我压根儿就没在乎输赢，虽然知道赌约就这么几句话很可能钻空子刻意回避一
些难题，但是也就大致扫了几眼压根没细想就度假去了，只想着回来能看到东西赶紧结
束。goodbug是不是我这么想的我不知道，如果不是人家已经杀档也没办法看到你说他
智商情商有问题。
可是你总知道甲方乙方或者做软件外包的商业合同是啥样的吧？ 你也知道赌约中没有
说清楚的地方可以按照最坏解释原则吧？ 我都懒得挑刺认输赶紧结束他们高兴就好。
这样以来，不管赌约如何， code摆在那， 每个人有每个人的解读， 我不反对别人觉
得高深莫测，可我觉得这就是个美本cs 1**的 toy project， 当然我也承认有些c++的
语法我没看懂， 不过这program干了什么摆在那就是了。 看到姓wei的为1us的优化讨
论的煞有其事的模样真是逗，说到底现代真正的web services就特么不是这么做的，
因为做web的瓶颈就tm从来不在mem和local上: https://gist.github.com/jboner/
2841832
【在 a*********a 的大作中提到】
: 你的意思是，一个里里外外吵了两年年的问题，古德霸还被魏耍了？魏“刻意简化，回
: 避瓶颈”，射了个套，古德霸还直接就钻了？
: 这是贬低古德霸的智商呢，还是贬低古德霸的情商呢？
:
: 相反我宁愿输钱输面子也想学点新东西
|
a*********a
发帖数: 3656 | 135 你参赌了？我一直以为是老魏，老古，一对一。
【在 k******n 的大作中提到】
:
: 还两年， 我刚进来几个星期看着那套做派都烦了， 这么吵下去威胁互相问候的整个版
: 都给污了， 你打人家脸人家不回重新开一个往复循环自说自话。 我的目的很简单，整
: 个topic赶紧结束所有人shut up最好。
: 接这赌约我压根儿就没在乎输赢，虽然知道赌约就这么几句话很可能钻空子刻意回避一
: 些难题，但是也就大致扫了几眼压根没细想就度假去了，只想着回来能看到东西赶紧结
: 束。goodbug是不是我这么想的我不知道，如果不是人家已经杀档也没办法看到你说他
: 智商情商有问题。
: 可是你总知道甲方乙方或者做软件外包的商业合同是啥样的吧？ 你也知道赌约中没有
: 说清楚的地方可以按照最坏解释原则吧？ 我都懒得挑刺认输赶紧结束他们高兴就好。
|
k******n
发帖数: 184 | 136
应该是1 v 3， 我和另一个看不惯姓wei威胁告hr的ID作风损了他几句和质疑技术问题
，他叫嚣着让我们3个人都赌才肯开始(当时语气非常不客气好像是"3个孙子"之类的)，
并且还有时间限制。我就同意了， 就算我输了总比版里变那样好吧， 至少有代码可以
看到底是个toy还是个什么。
另外一个id似乎在linear scalability问题上把姓wei的呛的不敢回复，我也没仔细看
他是否应下了， 不过应该不在赌约中。 这个赌约其实就是裁判庄家都是一个人， 纯
粹为赢而设计的。 输了没什么， 不过这样挺low的， 跑在mem上的就把一个web
service有挑战的问题全回避了。
【在 a*********a 的大作中提到】
: 你参赌了？我一直以为是老魏，老古，一对一。
|
a*********a
发帖数: 3656 | 137 另一个是？
【在 k******n 的大作中提到】
:
: 应该是1 v 3， 我和另一个看不惯姓wei威胁告hr的ID作风损了他几句和质疑技术问题
: ，他叫嚣着让我们3个人都赌才肯开始(当时语气非常不客气好像是"3个孙子"之类的)，
: 并且还有时间限制。我就同意了， 就算我输了总比版里变那样好吧， 至少有代码可以
: 看到底是个toy还是个什么。
: 另外一个id似乎在linear scalability问题上把姓wei的呛的不敢回复，我也没仔细看
: 他是否应下了， 不过应该不在赌约中。 这个赌约其实就是裁判庄家都是一个人， 纯
: 粹为赢而设计的。 输了没什么， 不过这样挺low的， 跑在mem上的就把一个web
: service有挑战的问题全回避了。
|
m*****k
发帖数: 731 | 138
4,
yes
yes, 也是暴力循环，但我猜总的来说出票时暴力循环貌似比查询时暴力循环省油。而
且把相关arr[i,j]的bit0置0的操作应该和老魏查询时复杂度等同。
【在 n*******7 的大作中提到】
: 按你的表达法，如果座0在站3到站5间有空，arr[3,5] 的bit0是1，arr[3,4］和arr[4,
: 5]的bit0 是1吗？
: 老魏的做法，在查询的时候需要看多个点，在出票的时候（transaction）只需要变一
: 到三个。如果
: 你查询时是O（1），在出票时需要改写多少地方？
:
: 么？
|
n*******7
发帖数: 181 | 139 老魏的做法是有道理的。查询部分不改写state，可以offload到其它cores，可以允许
多个cores同时查询（只读不写不需加锁），所以慢些没有关系；出票部分因为改写
state，需要快并且minimize改写部分，并且用dedicated core以免锁提高效率。这种
读写不对称处理还是很常见的。
老魏没有把东西做到底，因为已经够快就收手了。下一步应该是用一个core专做出票，
其它多个cores同时查询。那样的瓶颈就在出票上。出票简洁，只需改写一处，好处就
会出来了。你的办法出票时得搜索和改写多个地方，因为改写所以又不能多个cores同
时做，除非先锁住，速度就慢了。 |
a*********a
发帖数: 3656 | 140 看了一下你参赌的经过，觉得你做事很有问题。
1. 如果你目光犀利，判断准确，看出了魏过分简化，回避瓶颈，是个圈套，就应该明
确指出来，同时叫古不要赌。
2. 如果古水平没你高，没有看破这个“过分简化，回避瓶颈”的套，或者他知识有缺
陷，认为简化了也是mission
impossible，或者他头脑发热感情用事。那你就不该同意。这样你自己显得尿一点，
但是赌局不开，古德霸ID就不会死。
3. 既然你接了，就该好好帮着古德霸。结果你撒手度假去了。完了古德霸苦巴巴的在
斑上央求人做case test，没人理。
4. 结果出了，古德霸立即执行了，你还在这里唧唧歪歪。
你们门萨俱乐部都是你这样的猪队友吗？怎么感觉1v3的赌局，你把古德霸给卖了？
如果你觉得"3个孙子"语气非常不客气，魏如果说“3个太监”你的幼小心灵该受到多大
创伤啊？
【在 k******n 的大作中提到】
:
: 应该是1 v 3， 我和另一个看不惯姓wei威胁告hr的ID作风损了他几句和质疑技术问题
: ，他叫嚣着让我们3个人都赌才肯开始(当时语气非常不客气好像是"3个孙子"之类的)，
: 并且还有时间限制。我就同意了， 就算我输了总比版里变那样好吧， 至少有代码可以
: 看到底是个toy还是个什么。
: 另外一个id似乎在linear scalability问题上把姓wei的呛的不敢回复，我也没仔细看
: 他是否应下了， 不过应该不在赌约中。 这个赌约其实就是裁判庄家都是一个人， 纯
: 粹为赢而设计的。 输了没什么， 不过这样挺low的， 跑在mem上的就把一个web
: service有挑战的问题全回避了。
|
|
|
s*******r
发帖数: 310 | 141 其实很简单，就是自以为是的人没赌品，输不起。
在我看来这帮输家比人赢家老魏还嚣张。
mission
【在 a*********a 的大作中提到】
: 看了一下你参赌的经过，觉得你做事很有问题。
: 1. 如果你目光犀利，判断准确，看出了魏过分简化，回避瓶颈，是个圈套，就应该明
: 确指出来，同时叫古不要赌。
: 2. 如果古水平没你高，没有看破这个“过分简化，回避瓶颈”的套，或者他知识有缺
: 陷，认为简化了也是mission
: impossible，或者他头脑发热感情用事。那你就不该同意。这样你自己显得尿一点，
: 但是赌局不开，古德霸ID就不会死。
: 3. 既然你接了，就该好好帮着古德霸。结果你撒手度假去了。完了古德霸苦巴巴的在
: 斑上央求人做case test，没人理。
: 4. 结果出了，古德霸立即执行了，你还在这里唧唧歪歪。
|
p*******r
发帖数: 123 | 142 谷德宝还是有点水平的， 只是自视过高加嘴臭， 这位跟班就是纯粹来搞笑的， 又没
水平， 翻来翻去句那几句话， 老子年轻， 老子门得傻。。
【在 s*******r 的大作中提到】
: 其实很简单，就是自以为是的人没赌品，输不起。
: 在我看来这帮输家比人赢家老魏还嚣张。
:
: mission
|
k******n
发帖数: 184 | 143
不否认你说得很有道理啊， 可我就是在乎看最后的代码来着， 我不在乎吵架结果谁输
谁赢啊， 如果是我一起工作的teammates或者朋友吵架我自然会往好的方面处理。论坛
上这点破事至于我费心尽力么？ 大家都隔着网络面子值几个钱？吵完就关机睡觉了，
就你把网络上这点破面子当回事了。
你们最后能看到代码还应该感谢我当catalyst让赌局事态升级， 看了代码如何实现的
到底是好东西还是水货每个人的看法不同， 但是比版面污了强多了。就事论事
我怎么处理这种事情IQ有个毛关系，我从来没觉得自己IQ咋了，很多技术和代码一样不
懂。 最后送你一句人患在好为人师， 版里删了很多聊天记录， 吐脏话的你肯定看不
到了。 别觉得看了部分context就能占领道德高地了， 我最恶心这一套。
【在 a*********a 的大作中提到】
: 看了一下你参赌的经过，觉得你做事很有问题。
: 1. 如果你目光犀利，判断准确，看出了魏过分简化，回避瓶颈，是个圈套，就应该明
: 确指出来，同时叫古不要赌。
: 2. 如果古水平没你高，没有看破这个“过分简化，回避瓶颈”的套，或者他知识有缺
: 陷，认为简化了也是mission
: impossible，或者他头脑发热感情用事。那你就不该同意。这样你自己显得尿一点，
: 但是赌局不开，古德霸ID就不会死。
: 3. 既然你接了，就该好好帮着古德霸。结果你撒手度假去了。完了古德霸苦巴巴的在
: 斑上央求人做case test，没人理。
: 4. 结果出了，古德霸立即执行了，你还在这里唧唧歪歪。
|
k******n
发帖数: 184 | 144
姓wei的跟班也就这个水平了， 门得傻也是回应你们头的狗嘴里吐不出象牙的脏话，
上下文都看不利索 LOL
【在 p*******r 的大作中提到】
: 谷德宝还是有点水平的， 只是自视过高加嘴臭， 这位跟班就是纯粹来搞笑的， 又没
: 水平， 翻来翻去句那几句话， 老子年轻， 老子门得傻。。
|
k******n
发帖数: 184 | 145
我赌之前就声明了我不赌任何东西， 包括自杀id这种事情。 最后我也认输了， 请问
什么叫做嚣张？
如果有一说一， 这事儿压根就不应该上赌约， 姓wei的提出赌约杀id的时候你们就应
当制止。 最后刻意设计一个赌局做了个toy，离最基本的LAMP web services都差远了
瓶颈全部刻意为了赢赌局， 自己做庄家又做裁判的赌局你们见过么？ 那时候你们在哪
？现在到来道貌岸然指责别人还有啥可说的？
我完全可以缩卵可以跟大流， 但事情前后还是说清楚的好， 杀档也没什么， 这里也
不是学习技术的好地方。
【在 s*******r 的大作中提到】
: 其实很简单，就是自以为是的人没赌品，输不起。
: 在我看来这帮输家比人赢家老魏还嚣张。
:
: mission
|
p*****y
发帖数: 529 | 146 你在哪儿认输了， 我怎么觉得你赢了呢？
【在 k******n 的大作中提到】
:
: 我赌之前就声明了我不赌任何东西， 包括自杀id这种事情。 最后我也认输了， 请问
: 什么叫做嚣张？
: 如果有一说一， 这事儿压根就不应该上赌约， 姓wei的提出赌约杀id的时候你们就应
: 当制止。 最后刻意设计一个赌局做了个toy，离最基本的LAMP web services都差远了
: 瓶颈全部刻意为了赢赌局， 自己做庄家又做裁判的赌局你们见过么？ 那时候你们在哪
: ？现在到来道貌岸然指责别人还有啥可说的？
: 我完全可以缩卵可以跟大流， 但事情前后还是说清楚的好， 杀档也没什么， 这里也
: 不是学习技术的好地方。
|
T********i
发帖数: 2416 | 147 说实话，这版上平均水平啥样我心里也有数。
你这种水平的，还真确实少见。几句话就看出来了。
【在 k******n 的大作中提到】
:
: 我赌之前就声明了我不赌任何东西， 包括自杀id这种事情。 最后我也认输了， 请问
: 什么叫做嚣张？
: 如果有一说一， 这事儿压根就不应该上赌约， 姓wei的提出赌约杀id的时候你们就应
: 当制止。 最后刻意设计一个赌局做了个toy，离最基本的LAMP web services都差远了
: 瓶颈全部刻意为了赢赌局， 自己做庄家又做裁判的赌局你们见过么？ 那时候你们在哪
: ？现在到来道貌岸然指责别人还有啥可说的？
: 我完全可以缩卵可以跟大流， 但事情前后还是说清楚的好， 杀档也没什么， 这里也
: 不是学习技术的好地方。
|
s*******r
发帖数: 310 | 148 认输以后说人家为了赢赌局刻意简化问题，很Low啥的，当时立赌约是你为啥不
challenge？还有这么认输的，这不是输不起是什么？嘲笑人家年纪大，吹自己年轻是
门萨普通会员，这不是嚣张是什么？别跟我提什么上下文，最近两天的对骂都是你那酸
不垃圾的认输文起的头。
【在 k******n 的大作中提到】
:
: 我赌之前就声明了我不赌任何东西， 包括自杀id这种事情。 最后我也认输了， 请问
: 什么叫做嚣张？
: 如果有一说一， 这事儿压根就不应该上赌约， 姓wei的提出赌约杀id的时候你们就应
: 当制止。 最后刻意设计一个赌局做了个toy，离最基本的LAMP web services都差远了
: 瓶颈全部刻意为了赢赌局， 自己做庄家又做裁判的赌局你们见过么？ 那时候你们在哪
: ？现在到来道貌岸然指责别人还有啥可说的？
: 我完全可以缩卵可以跟大流， 但事情前后还是说清楚的好， 杀档也没什么， 这里也
: 不是学习技术的好地方。
|
k******n
发帖数: 184 | 149
别人的不回， 就单独认真回你一段。
“ 认输以后说人家为了赢赌局刻意简化问题，很Low啥的，当时立赌约是你为啥不
我早说过接下赌约是为了让事情早点结束，我并不在乎输赢和自己的面子， 代码出来
大家就知道写了什么， 比过年之前每天被开新帖刷版事情毫无进展好太多。 然而事实
上赌约渺渺几行字是可以按照最坏原则解读的， 包括tests是否包含remote call这些
， 包括是否是一个完整的web services以及linear scalability到底算不算进去我统
统没有计较， 即使我知道。(但凡有些工作经验的都知道做软件外包合同如何详尽）
如果我真的需要使坏一开始不接即可，或者版里风向变了缩卵即可， 只是没想到我刻
意促进事态升级结束反倒被埋怨起来了。
“嘲笑人家年纪大，吹自己年轻是
这句话是回应姓wei的"你的智商都被狗吃了"的脏话， 如果你觉得我的回应很装逼这我
可以理解。我回复之后姓wei的如何回复你也可以看看， 我当然只有损几句他了。 如
果说之前的掐架中好虫一直嘴臭， 那么姓wei的嘴巴也少不了屎， 至于别的什么脏话
威胁的破事就不提了。你戴有色眼镜忽略这些很正常。
“别跟我提什么上下文，最近两天的对骂都是你那酸
我花了大概一个下午的时间读和确认源码，基本知道这些代码做了什么。每个人有自己
的解读， 我可以认输， 但这就是个单机toy, 还是跑在mem上用data structure模拟
db的玩具。 赌约的初衷至少应该是解决问题， 哪怕用虚拟机模拟一个node做db
server专门用来r/w我都不会说什么，这好歹也算模拟了一个bottole neck, 但是做的
这个东西纯粹是为了赢而设计的赌局完全违背了这个版存在的初衷以及骂架的中心点。
本来还指着业余看这版能学些经验谈，卷进个这个破事也真可笑的， 还真是劣币驱逐
良币， 什么赌约把在版上解答过很多技术问题的好虫赶跑了。
【在 s*******r 的大作中提到】
: 认输以后说人家为了赢赌局刻意简化问题，很Low啥的，当时立赌约是你为啥不
: challenge？还有这么认输的，这不是输不起是什么？嘲笑人家年纪大，吹自己年轻是
: 门萨普通会员，这不是嚣张是什么？别跟我提什么上下文，最近两天的对骂都是你那酸
: 不垃圾的认输文起的头。
|
s*******r
发帖数: 310 | 150 我也最后回你一贴，要么认赌服输闭嘴，要么就不要认输继续战斗，如果你仍然觉得自
己在理。古德霸如果只是认输自杀ID不要继续骂人阉党太监，形象会高大很多。另外，
老魏不该说智商被狗吃了这种话，但是你嘲笑别人年纪大，吹自己年轻是门萨会员啥的
真的更亮瞎别人狗眼，下次换个应对法，LOL。
【在 k******n 的大作中提到】
:
: 别人的不回， 就单独认真回你一段。
: “ 认输以后说人家为了赢赌局刻意简化问题，很Low啥的，当时立赌约是你为啥不
: 我早说过接下赌约是为了让事情早点结束，我并不在乎输赢和自己的面子， 代码出来
: 大家就知道写了什么， 比过年之前每天被开新帖刷版事情毫无进展好太多。 然而事实
: 上赌约渺渺几行字是可以按照最坏原则解读的， 包括tests是否包含remote call这些
: ， 包括是否是一个完整的web services以及linear scalability到底算不算进去我统
: 统没有计较， 即使我知道。(但凡有些工作经验的都知道做软件外包合同如何详尽）
: 如果我真的需要使坏一开始不接即可，或者版里风向变了缩卵即可， 只是没想到我刻
: 意促进事态升级结束反倒被埋怨起来了。
|
|
|
n*******7
发帖数: 181 | 151 这个楼歪得可以。让我们回到算法上来。
前面有人抱怨老魏code对存范围的二维数组的搜索是暴力解。我的理解是这是有
tradeoff的优化，针对小站数和大座位数，牺牲对站数的scalability，换得对座位数
的O(1). 对10站最多搜55次，取座时直接从stack上pop。如果没有这个二维数组，而
是对座位一个一个的搜，3000个座位，在座位大半满的情况下，要读多少次才能找到空
座或确定没有空座？那才是真正的暴力。
有可能当前这种算法不是最优。请大家想想有没有更好算法。 |
m*****k
发帖数: 731 | 152 没人说不要这个二维数组吧。
感谢提醒，站数n<=50比较实际。站数和座位数比起来确实小多了，即使n^2也赶不上，
直接从有限几个stack上pop，push应该比在O(n^2)个3000bit上置0置1快。
这就是请教讨论的目的，学习自己没想到的，开阔眼界，查漏补缺，绝没有抱怨之意。
感谢老姜，老魏，nanxiang7都来不及呢！
【在 n*******7 的大作中提到】
: 这个楼歪得可以。让我们回到算法上来。
: 前面有人抱怨老魏code对存范围的二维数组的搜索是暴力解。我的理解是这是有
: tradeoff的优化，针对小站数和大座位数，牺牲对站数的scalability，换得对座位数
: 的O(1). 对10站最多搜55次，取座时直接从stack上pop。如果没有这个二维数组，而
: 是对座位一个一个的搜，3000个座位，在座位大半满的情况下，要读多少次才能找到空
: 座或确定没有空座？那才是真正的暴力。
: 有可能当前这种算法不是最优。请大家想想有没有更好算法。
|
p*****y
发帖数: 529 | 153 是个爷们就shut up. 这点上好虫比你多了两balls。
【在 k******n 的大作中提到】
:
: 别人的不回， 就单独认真回你一段。
: “ 认输以后说人家为了赢赌局刻意简化问题，很Low啥的，当时立赌约是你为啥不
: 我早说过接下赌约是为了让事情早点结束，我并不在乎输赢和自己的面子， 代码出来
: 大家就知道写了什么， 比过年之前每天被开新帖刷版事情毫无进展好太多。 然而事实
: 上赌约渺渺几行字是可以按照最坏原则解读的， 包括tests是否包含remote call这些
: ， 包括是否是一个完整的web services以及linear scalability到底算不算进去我统
: 统没有计较， 即使我知道。(但凡有些工作经验的都知道做软件外包合同如何详尽）
: 如果我真的需要使坏一开始不接即可，或者版里风向变了缩卵即可， 只是没想到我刻
: 意促进事态升级结束反倒被埋怨起来了。
|
n*******7
发帖数: 181 | 154 是我不该用“抱怨”这个词。我自己也希望没有这个站数scalability的限制。
你太客气了。我也是在向你们学习中。
【在 m*****k 的大作中提到】
: 没人说不要这个二维数组吧。
: 感谢提醒，站数n<=50比较实际。站数和座位数比起来确实小多了，即使n^2也赶不上，
: 直接从有限几个stack上pop，push应该比在O(n^2)个3000bit上置0置1快。
: 这就是请教讨论的目的，学习自己没想到的，开阔眼界，查漏补缺，绝没有抱怨之意。
: 感谢老姜，老魏，nanxiang7都来不及呢！
|
k****i
发帖数: 101 | 155 pure brute force algo below, slower than TeacherWei's, nevertheless in line
with the order of magnitude.
-----------
#include
#include
#include
#include
#define TRAINS 5000
#define SEGMENTS 10
#define SEATS 3000
#define REQUESTS 40000000
using namespace boost::multiprecision;
cpp_int _SEATS_ (0);
cpp_int _seats_ [TRAINS][SEGMENTS];
void init()
{
for (int seat = 0; seat < SEATS; seat++)
bit_set(_SEATS_, seat);
for (int train = 0; train < TRAINS; train++)
for (int segment = 0; segment < SEGMENTS; segment++)
_seats_[train][segment] = _SEATS_;
}
void run()
{
for(int i = 0; i < REQUESTS; i++)
{
int train = rand() % TRAINS;
int start = rand() % SEGMENTS;
int stop = rand() % (SEGMENTS - start) + start + 1;
cpp_int seats = _SEATS_;
for (int segment = start; segment < stop; segment++)
seats &= _seats_[train][segment];
try
{
int seat = lsb(seats);
for (int segment = start; segment < stop; segment++)
bit_unset(_seats_[train][segment], seat);
}
catch(std::exception e)
{
}
}
}
int main()
{
init();
timespec t;
clock_gettime(CLOCK_REALTIME, &t);
run();
timespec t2;
clock_gettime(CLOCK_REALTIME, &t2);
long diff = (t2.tv_sec - t.tv_sec) * 1000000000 +
(t2.tv_nsec - t.tv_nsec);
std::cout << diff / REQUESTS << " ns/req" << std::endl;
}
【在 n*******7 的大作中提到】
: 放假，终于有时间run GDB，才对老魏的程序有些理解了。仍然有些疑问。想向老魏和
: 大家请教。
: 先陈述一下基本的理解：
: TrainTicketMap 是关键的数据库，表征对应车次当前所有空座. 它是一个二维数组，
: 两个indices分别是起始站和（站数 - 1). 它的值是一个stack（由单向链实现）。
: stack上每一元素对应一个座位的站次间的空座范围，表示此座位从该起始站开始数该
: 站数范围内是空的。该元素的next指针指向stack上下一个对应不同座位的元素。
: 在初始状态，每个座位从起始站0开始10站都空，所以这个二维数组只在index［0，9］
: 有非空stack，里面压了对应所有座位的3000个元素，座位1在最上。假设第一个请求是
: 起始站3站数1，则座位1从站3到站4被出票，该座位空座范围［起始站，站数－1］从［
|
w******w
发帖数: 126 | |
k****i
发帖数: 101 | 157 pure brute force algo below, slower than TeacherWei's, nevertheless in line
with the order of magnitude.
-----------
#include
#include
#include
#include
#define TRAINS 5000
#define SEGMENTS 10
#define SEATS 3000
#define REQUESTS 40000000
using namespace boost::multiprecision;
cpp_int _SEATS_ (0);
cpp_int _seats_ [TRAINS][SEGMENTS];
void init()
{
for (int seat = 0; seat < SEATS; seat++)
bit_set(_SEATS_, seat);
for (int train = 0; train < TRAINS; train++)
for (int segment = 0; segment < SEGMENTS; segment++)
_seats_[train][segment] = _SEATS_;
}
void run()
{
for(int i = 0; i < REQUESTS; i++)
{
int train = rand() % TRAINS;
int start = rand() % SEGMENTS;
int stop = rand() % (SEGMENTS - start) + start + 1;
cpp_int seats = _SEATS_;
for (int segment = start; segment < stop; segment++)
seats &= _seats_[train][segment];
try
{
int seat = lsb(seats);
for (int segment = start; segment < stop; segment++)
bit_unset(_seats_[train][segment], seat);
}
catch(std::exception e)
{
}
}
}
int main()
{
init();
timespec t;
clock_gettime(CLOCK_REALTIME, &t);
run();
timespec t2;
clock_gettime(CLOCK_REALTIME, &t2);
long diff = (t2.tv_sec - t.tv_sec) * 1000000000 +
(t2.tv_nsec - t.tv_nsec);
std::cout << diff / REQUESTS << " ns/req" << std::endl;
}
【在 n*******7 的大作中提到】
: 放假，终于有时间run GDB，才对老魏的程序有些理解了。仍然有些疑问。想向老魏和
: 大家请教。
: 先陈述一下基本的理解：
: TrainTicketMap 是关键的数据库，表征对应车次当前所有空座. 它是一个二维数组，
: 两个indices分别是起始站和（站数 - 1). 它的值是一个stack（由单向链实现）。
: stack上每一元素对应一个座位的站次间的空座范围，表示此座位从该起始站开始数该
: 站数范围内是空的。该元素的next指针指向stack上下一个对应不同座位的元素。
: 在初始状态，每个座位从起始站0开始10站都空，所以这个二维数组只在index［0，9］
: 有非空stack，里面压了对应所有座位的3000个元素，座位1在最上。假设第一个请求是
: 起始站3站数1，则座位1从站3到站4被出票，该座位空座范围［起始站，站数－1］从［
|
w******w
发帖数: 126 | |
w******w
发帖数: 126 | |
