Re: [systemd-devel] [PATCH] prioq: avoid to swap item index

2013-12-16 Thread Lennart Poettering 
On Mon, 16.12.13 13:15, Yang Chengwei (chengwei.y...@intel.com) wrote:

 On Mon, Dec 16, 2013 at 04:57:39AM +0100, Lennart Poettering wrote:
  On Mon, 16.12.13 04:48, Lennart Poettering (lenn...@poettering.net) wrote:
  
   
   On Mon, 16.12.13 11:03, Chengwei Yang (chengwei.y...@intel.com) wrote:
   
the swap() operation of prioq which in fact only swap item's data but
keep idx untouched. However, current implement does first swap the idx
and then swap back again.
   
   Sorry, I do understand? Can you elaborate, please? Is this supposed to
   wanted to say: I do *not* understand...
 
 It's an optimization.
 
 A condition of the queue is just like the assert says
 
 assert(!q-items[j].idx || *(q-items[j].idx) == j);
 assert(!q-items[k].idx || *(q-items[k].idx) == k);
 
 This is true before and after swap. So in fact no need to swap idx and
 then swap back again. Just do not touch idx, then item[j].idx is always
 0 or j, so as item[k].
 
 The deleted code does
 
 1. first swap the idx regardless it's 0 or not
 
 2. then, if idx isn't 0, swap back.
 
 So this patch is a optimization for the case where item.idx isn't 0,
 which avoid to swap idx and swap idx back.
 
 I'm not sure this is clear enough. In simple, the fact is *before* and
 *after* we need make sure item[j].idx == j or item[j].idx == 0, so why we
 change it during swap? Because if it changed during swap, we need then
 assign item[j].idx = j before the swap finish. So the simple way is keep
 it untouched.

Sorry, still not getting what you want to say.

Mayb ethere is some confusion regarding what .idx actually is? .idx is
supposed to point to some index integer that is stored in the actual
structure the user added to the priority queue and that can be used to
quickly remove an entry from the priority queue without requiring it to
be the first one. 

In the swap() call we hence first swap the the data and idx pointers
themselves, and then in a second step we finally update what the idx
pointers actually point to to the new index of the item in our priority
queue.

I totally don't see how any of that was redundant. We must make sure
after all that after the swap:

a) For both entries we know that the data pointer has been swapped
b) For both entries we know that the pointer to the index value that is part of 
the user structure has been swapped
c) For both entries we know that the index value that is part of the user 
structure has been swapped

Lennart

-- 
Lennart Poettering, Red Hat
___
systemd-devel mailing list
systemd-devel@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/systemd-devel

[systemd-devel] [PATCH] prioq: avoid to swap item index

2013-12-15 Thread Chengwei Yang 
the swap() operation of prioq which in fact only swap item's data but
keep idx untouched. However, current implement does first swap the idx
and then swap back again.
---
 src/shared/prioq.c |   10 --
 1 file changed, 10 deletions(-)

diff --git a/src/shared/prioq.c b/src/shared/prioq.c
index 8af4c51..ef99c47 100644
--- a/src/shared/prioq.c
+++ b/src/shared/prioq.c
@@ -68,7 +68,6 @@ int prioq_ensure_allocated(Prioq **q, compare_func_t 
compare_func) {
 
 static void swap(Prioq *q, unsigned j, unsigned k) {
 void *saved_data;
-unsigned *saved_idx;
 
 assert(q);
 assert(j  q-n_items);
@@ -78,17 +77,8 @@ static void swap(Prioq *q, unsigned j, unsigned k) {
 assert(!q-items[k].idx || *(q-items[k].idx) == k);
 
 saved_data = q-items[j].data;
-saved_idx = q-items[j].idx;
 q-items[j].data = q-items[k].data;
-q-items[j].idx = q-items[k].idx;
 q-items[k].data = saved_data;
-q-items[k].idx = saved_idx;
-
-if (q-items[j].idx)
-*q-items[j].idx = j;
-
-if (q-items[k].idx)
-*q-items[k].idx = k;
 }
 
 static unsigned shuffle_up(Prioq *q, unsigned idx) {
-- 
1.7.9.5

___
systemd-devel mailing list
systemd-devel@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/systemd-devel

Re: [systemd-devel] [PATCH] prioq: avoid to swap item index

2013-12-15 Thread Lennart Poettering 
On Mon, 16.12.13 11:03, Chengwei Yang (chengwei.y...@intel.com) wrote:

 the swap() operation of prioq which in fact only swap item's data but
 keep idx untouched. However, current implement does first swap the idx
 and then swap back again.

Sorry, I do understand? Can you elaborate, please? Is this supposed to
be a bug fix or an optimization?

 ---
  src/shared/prioq.c |   10 --
  1 file changed, 10 deletions(-)
 
 diff --git a/src/shared/prioq.c b/src/shared/prioq.c
 index 8af4c51..ef99c47 100644
 --- a/src/shared/prioq.c
 +++ b/src/shared/prioq.c
 @@ -68,7 +68,6 @@ int prioq_ensure_allocated(Prioq **q, compare_func_t 
 compare_func) {
  
  static void swap(Prioq *q, unsigned j, unsigned k) {
  void *saved_data;
 -unsigned *saved_idx;
  
  assert(q);
  assert(j  q-n_items);
 @@ -78,17 +77,8 @@ static void swap(Prioq *q, unsigned j, unsigned k) {
  assert(!q-items[k].idx || *(q-items[k].idx) == k);
  
  saved_data = q-items[j].data;
 -saved_idx = q-items[j].idx;
  q-items[j].data = q-items[k].data;
 -q-items[j].idx = q-items[k].idx;
  q-items[k].data = saved_data;
 -q-items[k].idx = saved_idx;
 -
 -if (q-items[j].idx)
 -*q-items[j].idx = j;
 -
 -if (q-items[k].idx)
 -*q-items[k].idx = k;
  }
  
  static unsigned shuffle_up(Prioq *q, unsigned idx) {


Lennart

-- 
Lennart Poettering, Red Hat
___
systemd-devel mailing list
systemd-devel@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/systemd-devel

Re: [systemd-devel] [PATCH] prioq: avoid to swap item index

2013-12-15 Thread Lennart Poettering 
On Mon, 16.12.13 04:48, Lennart Poettering (lenn...@poettering.net) wrote:

 
 On Mon, 16.12.13 11:03, Chengwei Yang (chengwei.y...@intel.com) wrote:
 
  the swap() operation of prioq which in fact only swap item's data but
  keep idx untouched. However, current implement does first swap the idx
  and then swap back again.
 
 Sorry, I do understand? Can you elaborate, please? Is this supposed to
 wanted to say: I do *not* understand...
 be a bug fix or an optimization?
 
  ---
   src/shared/prioq.c |   10 --
   1 file changed, 10 deletions(-)
  
  diff --git a/src/shared/prioq.c b/src/shared/prioq.c
  index 8af4c51..ef99c47 100644
  --- a/src/shared/prioq.c
  +++ b/src/shared/prioq.c
  @@ -68,7 +68,6 @@ int prioq_ensure_allocated(Prioq **q, compare_func_t 
  compare_func) {
   
   static void swap(Prioq *q, unsigned j, unsigned k) {
   void *saved_data;
  -unsigned *saved_idx;
   
   assert(q);
   assert(j  q-n_items);
  @@ -78,17 +77,8 @@ static void swap(Prioq *q, unsigned j, unsigned k) {
   assert(!q-items[k].idx || *(q-items[k].idx) == k);
   
   saved_data = q-items[j].data;
  -saved_idx = q-items[j].idx;
   q-items[j].data = q-items[k].data;
  -q-items[j].idx = q-items[k].idx;
   q-items[k].data = saved_data;
  -q-items[k].idx = saved_idx;
  -
  -if (q-items[j].idx)
  -*q-items[j].idx = j;
  -
  -if (q-items[k].idx)
  -*q-items[k].idx = k;
   }
   
   static unsigned shuffle_up(Prioq *q, unsigned idx) {
 
 
 Lennart
 


Lennart

-- 
Lennart Poettering, Red Hat
___
systemd-devel mailing list
systemd-devel@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/systemd-devel

Re: [systemd-devel] [PATCH] prioq: avoid to swap item index

2013-12-15 Thread Yang Chengwei 
On Mon, Dec 16, 2013 at 04:57:39AM +0100, Lennart Poettering wrote:
 On Mon, 16.12.13 04:48, Lennart Poettering (lenn...@poettering.net) wrote:
 
  
  On Mon, 16.12.13 11:03, Chengwei Yang (chengwei.y...@intel.com) wrote:
  
   the swap() operation of prioq which in fact only swap item's data but
   keep idx untouched. However, current implement does first swap the idx
   and then swap back again.
  
  Sorry, I do understand? Can you elaborate, please? Is this supposed to
  wanted to say: I do *not* understand...

It's an optimization.

A condition of the queue is just like the assert says

assert(!q-items[j].idx || *(q-items[j].idx) == j);
assert(!q-items[k].idx || *(q-items[k].idx) == k);

This is true before and after swap. So in fact no need to swap idx and
then swap back again. Just do not touch idx, then item[j].idx is always
0 or j, so as item[k].

The deleted code does

1. first swap the idx regardless it's 0 or not

2. then, if idx isn't 0, swap back.

So this patch is a optimization for the case where item.idx isn't 0,
which avoid to swap idx and swap idx back.

I'm not sure this is clear enough. In simple, the fact is *before* and
*after* we need make sure item[j].idx == j or item[j].idx == 0, so why we
change it during swap? Because if it changed during swap, we need then
assign item[j].idx = j before the swap finish. So the simple way is keep
it untouched.

--
Thanks,
Chengwei

  be a bug fix or an optimization?
  
   ---
src/shared/prioq.c |   10 --
1 file changed, 10 deletions(-)
   
   diff --git a/src/shared/prioq.c b/src/shared/prioq.c
   index 8af4c51..ef99c47 100644
   --- a/src/shared/prioq.c
   +++ b/src/shared/prioq.c
   @@ -68,7 +68,6 @@ int prioq_ensure_allocated(Prioq **q, compare_func_t 
   compare_func) {

static void swap(Prioq *q, unsigned j, unsigned k) {
void *saved_data;
   -unsigned *saved_idx;

assert(q);
assert(j  q-n_items);
   @@ -78,17 +77,8 @@ static void swap(Prioq *q, unsigned j, unsigned k) {
assert(!q-items[k].idx || *(q-items[k].idx) == k);

saved_data = q-items[j].data;
   -saved_idx = q-items[j].idx;
q-items[j].data = q-items[k].data;
   -q-items[j].idx = q-items[k].idx;
q-items[k].data = saved_data;
   -q-items[k].idx = saved_idx;
   -
   -if (q-items[j].idx)
   -*q-items[j].idx = j;
   -
   -if (q-items[k].idx)
   -*q-items[k].idx = k;
}

static unsigned shuffle_up(Prioq *q, unsigned idx) {
  
  
  Lennart
  
 
 
 Lennart
 
 -- 
 Lennart Poettering, Red Hat


signature.asc
Description: Digital signature
___
systemd-devel mailing list
systemd-devel@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/systemd-devel